3

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

我们必须在不同的柱子（如锁）上排列不同的数字来解锁密码。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，并且您拥有所有可能的组合。

谁能指出我正确的方向，以另一种算法来补充这个左右？

4

5 回答 5

8

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，否则您将在用尽所有排列之前停止。

于 2013-02-27T03:09:45.843 回答
1

如果您需要自己实现，这可能无济于事，但 C++ 已next_permutation内置。

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

这里解释了这个函数背后的算法：std::next_permutation Implementation Explanation

于 2013-02-27T03:09:34.247 回答
1

从 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;
}
于 2013-02-27T03:21:28.233 回答
0

首先，让我们谈谈你的问题是打印集合 {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

于 2013-02-27T06:44:01.993 回答
0

此函数使用 bitset 列出所有排列

#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;
}
于 2020-03-30T00:50:57.290 回答