python - 如何在C++中使用STL在低于总长度的位数下创建排列

我有一个带有c++ vector对象的std::pair<unsigned long, unsigned long>。我正在尝试使用std::next_permutation()生成 vector 对象的排列。但是,我希望排列具有给定的大小,类似于python中的permutations函数,其中指定了预期返回的排列的大小。

基本上,c++等效于

import itertools

list = [1,2,3,4,5,6,7]
for permutation in itertools.permutations(list, 3):
    print(permutation)

Python Demo
(1, 2, 3)                                                                                                                                                                            
(1, 2, 4)                                                                                                                                                                            
(1, 2, 5)                                                                                                                                                                            
(1, 2, 6)                                                                                                                                                                            
(1, 2, 7)                                                                                                                                                                            
(1, 3, 2)
(1, 3, 4)
..
(7, 5, 4)                                                                                                                                                                            
(7, 5, 6)                                                                                                                                                                            
(7, 6, 1)                                                                                                                                                                            
(7, 6, 2)                                                                                                                                                                            
(7, 6, 3)                                                                                                                                                                            
(7, 6, 4)                                                                                                                                                                            
(7, 6, 5) 

最佳答案

您可以使用2个循环:

  • 取每个n元组
  • 遍历该n元组
  • 的排列
    template <typename F, typename T>
    void permutation(F f, std::vector<T> v, std::size_t n)
    {
        std::vector<bool> bs(v.size() - n, false);
        bs.resize(v.size(), true);
        std::sort(v.begin(), v.end());
    
        do {
            std::vector<T> sub;
            for (std::size_t i = 0; i != bs.size(); ++i) {
                if (bs[i]) {
                    sub.push_back(v[i]);
                }
            }
            do {
                f(sub);
            }
            while (std::next_permutation(sub.begin(), sub.end()));
        } while (std::next_permutation(bs.begin(), bs.end()));
    }
    

    Demo