c++ - 没有递归的排列？

Question

我试图使用 for 循环来替换我通常使用的递归，但我发现它比我想象的要难。谁能告诉我该怎么做？谢谢！

例如，给定一个 2、1、3 的向量。应该有六个排列：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

向量如下...

vector<int> simple;
simple.push_back(2);
simple.push_back(1);
simple.push_back(3);

编辑：将顺序从 1 2 3 更改为随机顺序 2 1 3

Answer 1

我猜你正在寻找std::next_permutation()：

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

int main()
{
    std::vector<int> simple{1, 2, 3};

    do
    {
        for (auto e : simple) { std::cout << e << " "; }
        std::cout << std::endl;
    }
    while (next_permutation(simple.begin(), simple.end()));
}

这是一个活生生的例子。

如果不想从排序向量开始，可以使用std::next_permutation()以下方式：

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

constexpr int factorial(int i)
{
    return i == 0 ? 1 : i * factorial(i-1);
}

int main()
{
    std::vector<int> simple{3, 1, 2};

    for (int i = 0; i < factorial(simple.size()); i++)
    {
        std::next_permutation(simple.begin(), simple.end());
        for (auto e : simple) { std::cout << e << " "; }
        std::cout << std::endl;
    }
}

这是一个活生生的例子。

请注意，如果向量的大小在编译时是已知的，就像您的示例中的情况一样，您可以使用std::array而不是std::vector，如此实时示例中所示。