C++向量的所有组合

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可以实现这个的平滑方式？

- NaCl

---

首先迭代查找所有可能的s数字集合，然后使用std::next_permutation函数？ - T.C.

大小为s中的 scramble 是什么意思？ - 101010

http://home.roadrunner.com/~hinnant/combinations.html - T.C.

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';
}

蓝 红 青绿 | 蓝 青绿 红 | 红 蓝 青绿 | 红 青绿 蓝 | 青绿 蓝 红 | 青绿 红 蓝 | 蓝 红 绿 | 蓝 绿 红 | 红 蓝 绿 | 红 绿 蓝 | 绿 蓝 红 | 绿 红 蓝 | 蓝 青绿 绿 | 蓝 绿 青绿 | 青绿 蓝 绿 | 青绿 绿 蓝 | 绿 蓝 青绿 | 绿 青绿 蓝 | 红 青绿 绿 | 红 绿 青绿 | 青绿 红 绿 | 青绿 绿 红 | 绿 红 青绿 | 绿 青绿 红 |

- Howard Hinnant

Answer 2

LIVE DEMO

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

void dfs(int depth, int s, int i, std::vector<int>& c, const std::vector<int>& v)
{
    if (depth == s)
    {
        do
        {
            std::copy(c.begin(), c.end(), std::ostream_iterator<int>(std::cout, " "));
            std::cout << "| ";
        }
        while (std::next_permutation(c.begin(), c.end()));
    }
    else
    {
        for (int j = i + 1; j < (int)v.size(); ++j)
        {
            c.push_back(v[j]);
            dfs(depth + 1, s, j, c, v);
            c.pop_back();
        }
    }
}

int main()
{
    std::vector<int> v{ 0, 1, 2, 3 };
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());    
    std::vector<int> c;
    const int length = 3;
    dfs(0, length, -1, c, v);
}

输出：

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

- Piotr Skotnicki

---

你的答案非常优雅，能否请您解释一下您的想法？ - GoingMyWay