c++ - 排列算法

Question

这是一个类，所以请不要太具体，但我正在寻找一种方法来列出数字数组的所有排列。

我们必须在不同的柱子(如锁)上排列不同的数字才能解锁组合。 4 根柱子上可能有 6 个数字。但它应该适用于 r 上的任何 n，只要 n > r。

我有办法随机生成组合，并有条不紊地在列表中查找它，但我无法生成生成所有排列的算法。

我能够在 C++ 中使用此方法获得数字 1-6 的所有组合:

//n = number of digits - 1; list = list of digits to work with; 
//number=finalized list of digits
void permute(int n, vector<int> list, vector<vector<int>>* number)
{
    if(n==1)
    {
        number->push_back(list);

    }else
    {
        for(int i = 1;i<n;i++)
        {
            permute(n-1,list, number);
            if(n%2 == 0)
            {
                swap(list[1],list[n]);
            }else
            {
                swap(list[i],list[n]);
            }
        }
    }

};

但是我得到了一个列表，比如 123456 163452 等等，其中 1 始终是第一个数字 但我还需要获得第一个数字何时切换并且只存在 4 位数字。

例子

6341

4163

等等，其中有 4 个数字，范围从 1 到 6，您有所有可能的组合。

谁能给我指出正确的方向，让我找到另一种算法来补充这一点？

Answer 1

C++ 为此提供了一个完美的解决方案——它是 std::next_permutation (您需要包含 <algorithms> 才能使用它)。

vector<int> list;
std::sort(list.begin(), list.end());
do {
    // use the current permutation of the list
} while (std::next_permutation(list.begin(), list.end()));

关于此函数要记住的重要一点是，如果您想遍历一个范围的所有 排列，则必须在第一次调用next_permuration 之前对该范围进行排序。 ，否则你将在用尽所有排列之前停止。