排列算法

Question

这是一门课程，所以请不要过于具体，但我正在寻找一种列出数字数组所有排列方式的方法。

我们必须在不同的柱子（就像锁）上排列不同的数字才能解开组合。每个柱子上可能有6个数字。只要n>r，它应该适用于任何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，您拥有所有可能的组合。

是否有人可以指导我使用另一种算法来补充这个问题？

- Chris

---

可能是std::next_permutation实现解释的重复问题。 - StilesCrisis

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之前，该范围必须先进行排序，否则你将在枚举所有排列组合之前停止。

- Sergey Kalinichenko

---

非常好的回复！还要注意库被称为<algorithm>而不是<algorithms>。 - Jake

Answer 2

如果您需要自己实现，这可能没有帮助，但是C ++内置了next_permutation。

http://www.cplusplus.com/reference/algorithm/next_permutation/

这个函数背后的算法在这里解释：std::next_permutation实现解释。

- StilesCrisis

Answer 3

一个通用的递归算法，用于从N个项目的列表中递归生成N长度的排列，具体步骤如下：

对于列表中的每个元素x，

复制不包含元素x的列表，称其为newList

找出newList的所有排列（这是递归过程）

将元素x添加到newList的每个排列的开头

#include <iostream>
#include <list>

typedef std::list<int> IntList;
void iterlist(IntList& lst)
{
    for (IntList::iterator it=lst.begin(); it!=lst.end(); it++)
        cout << " " << *it;
    cout << endl;
}

std::list<IntList> permute(IntList& L1)
{
    if (L1.size() == 1)
        return std::list<IntList>(1,L1);

    std::list<IntList> res;
    for (IntList::iterator i = L1.begin(); i != L1.end();)
    {
        // remember this
        int x = (*i);

        // make a list without the current element
        IntList tmp(L1.begin(), i++);
        tmp.insert(tmp.end(), i, L1.end());

        // recurse to get all sub-permutations
        std::list<IntList> sub = permute(tmp);

        // amend sub-permutations by adding the element
        for (std::list<IntList>::iterator j=sub.begin(); j!=sub.end();j++)
            (*j).push_front(x);

        // finally append modified results to our running collection.
        res.insert(res.begin(), sub.begin(), sub.end());
    }
    return res;
}

int main()
{
    IntList lst;
    for (int i=0;i<4;i++)
        lst.push_back(i);
    std::list<IntList> res = permute(lst);
    for (std::list<IntList>::iterator i=res.begin(); i!=res.end(); i++)
        iterlist(*i);
    return 0;
}

- Saqlain

---

谢谢！我喜欢你的做法！帮了很多忙！ - Chris

Answer 4

首先，让我们来谈谈你的问题，即如何打印出在集合{1,2,3,4,5,6}中所有P(6,4)数组的情况。但是，std::next_permutation只适用于所有元素的排列（P(6,6)），不适用于你的问题（P(6,4)）。

我认为使用std::next_permutation可以很容易地得到组合，而且由于我们知道P(6,4)=C(6,4)*P(4,4)，所以简单的代码实现可能像这样：

 1 #include <iostream>
  2 #include <vector>
  3
  4 int main()
  5 {
  6     std::vector<int> list;
  7     std::vector<int> subList;
  8     std::vector<bool> flag;
  9
 10     for (int i=1; i<=6; ++i)
 11         list.push_back(i);
 12     flag.insert(flag.end(),4,1);
 13     flag.insert(flag.end(),2,0);
 14     std::sort(flag.begin(), flag.end());
 15     do
 16     {
 17         subList.clear();
 18         for(int i=0; i<flag.size(); ++i)
 19         {
 20             if(flag[i])
 21             {
 22                 subList.push_back(list[i]);
 23             }
 24         }
 25         do
 26         {
 27             for(std::vector<int>::iterator it=subList.begin(); it!=subList.end(); ++it)
 28             {
 29                 std::cout << *it << " ";
 30             }
 31             std::cout << std::endl;
 32         }while(std::next_permutation(subList.begin(), subList.end()));
 33         std::cout << std::endl;
 34     } while(std::next_permutation(flag.begin(), flag.end()));
 35     return 0;
 36 }

显然，外层循环寻找C(6,4)，内层循环寻找P(4,4)。 对于组合问题，你可以使用搜索方法，就像DFS一样，参考：combinations of。

- A Lan

---

谢谢！这是一个非常酷的布尔运算使用方式；我以前从未见过。帮助我更好地理解了它！ - Chris

Answer 5

这个函数使用位集列出所有的排列组合

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

const int N = 3;

void permute(string_view s, bitset<N> &mask, string &pref)
{
    if (mask.all()) {
        cout << pref << endl;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!mask[i]) {
            mask.set(i);
            pref.push_back(s[i]);
            permute(s, mask, pref);
            pref.pop_back();
            mask.reset(i);
        }
    }
}

int main()
{
    string pref;
    bitset<N> mask;
    permute(string("abc"), mask, pref);
    return 0;
}

通过一些修改，它可以打印出所有的组合

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

const int N = 3;
const int M = 2;

void permute(string_view s, bitset<N> &mask, string &pref)
{
    if (pref.size() == M) {
        cout << pref << endl;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!mask[i]) {
            mask.set(i);
            permute(s, mask, pref);
            pref.push_back(s[i]);
            permute(s, mask, pref);
            pref.pop_back();
            mask.reset(i);
            break;
        }
    }
}

int main()
{
    string pref;
    bitset<N> mask;
    permute(string("abc"), mask, pref);
    return 0;
}

- ztyreg