排列算法

Question

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

我们必须在不同的支柱(如锁)上安排不同的数字来解锁组合.4个支柱中的每个支柱上可能有6个数字.但是只要n> r,它就适用于任何n.

我有办法随机生成一个组合,并有条不紊地在列表中查找它,但我在生成算法以生成所有排列时遇到问题.

我可以在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,否则你将在用完所有排列之前停止.