C++ vector 的所有组合

Question

假设我们有一些从 0 到 n 的数字，我们想要打乱那些大小为 s 的数字，并希望看到所有可能的组合。

所以排列的数量恰好等于s! * n!/(s!*(n-s)!)。

n = 3 和 s = 3 的示例:

0 1 2 | 0 1 3 | 0 2 1 | 0 2 3 | 0 3 1 | 0 3 2 | 1 0 2 | 1 0 3 | 1 3 2 
1 2 3 | 1 2 0 | 1 3 0 | 2 0 1 | 2 1 0 | 2 0 3 | 2 3 0 | 2 3 1 | 2 1 3
            3 0 1 | 3 1 0 | 3 0 2 | 3 2 0 | 3 1 2 | 3 2 1

是否有使用 boost/STL 的平滑方法来实现此目的？

Answer 1

这是使用 T.C. 链接的代码评论中提到的 ( http://howardhinnant.github.io/combinations.html ):

#include "../combinations/combinations"
#include <iostream>
#include <vector>

int
main()
{
    std::vector<int> v{0, 1, 2, 3};
    typedef std::vector<int>::iterator Iter;
    for_each_permutation(v.begin(), v.begin()+3, v.end(),
        [](Iter f, Iter l)
        {
            for (; f != l; ++f)
                std::cout << *f << ' ';
            std::cout << "| ";
            return false;
        }
    );
    std::cout << '\n';
}

0 1 2 | 0 2 1 | 1 0 2 | 1 2 0 | 2 0 1 | 2 1 0 | 0 1 3 | 0 3 1 | 1 0 3 | 1 3 0 | 3 0 1 | 3 1 0 | 0 2 3 | 0 3 2 | 2 0 3 | 2 3 0 | 3 0 2 | 3 2 0 | 1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1 | 

这个库相对于 std::next_permutation 的一个显着优势是被置换的元素不需要排序，甚至不需要小于可比性。例如:

#include "../combinations/combinations"
#include <iostream>
#include <vector>

enum class color
{
    red,
    green,
    blue,
    cyan
};

std::ostream&
operator<< (std::ostream& os, color c)
{
    switch (c)
    {
    case color::red:
        os << "red";
        break;
    case color::green:
        os << "green";
        break;
    case color::blue:
        os << "blue";
        break;
    case color::cyan:
        os << "cyan";
        break;
    }
    return os;
}

int
main()
{
    std::vector<color> v{color::blue, color::red, color::cyan, color::green};
    typedef std::vector<color>::iterator Iter;
    for_each_permutation(v.begin(), v.begin()+3, v.end(),
        [](Iter f, Iter l)
        {
            for (; f != l; ++f)
                std::cout << *f << ' ';
            std::cout << "| ";
            return false;
        }
    );
    std::cout << '\n';
}

blue red cyan | blue cyan red | red blue cyan | red cyan blue | cyan blue red | cyan red blue | blue red green | blue green red | red blue green | red green blue | green blue red | green red blue | blue cyan green | blue green cyan | cyan blue green | cyan green blue | green blue cyan | green cyan blue | red cyan green | red green cyan | cyan red green | cyan green red | green red cyan | green cyan red |