3

これはクラス用なので、あまり具体的にしないでください。ただし、数字の配列のすべての順列をリストする方法を探しています。

組み合わせのロックを解除するには、さまざまな柱 (ロックなど) にさまざまな数字を配置する必要があります。4 つの柱のそれぞれに 6 つの数字がある場合があります。ただし、n>r である限り、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

など、1 ～ 6 の範囲の 4 桁の数字があり、すべての可能な組み合わせがあります。

これを補完する別のアルゴリズムの正しい方向に誰かが私を向けることができますか?

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 実装の説明

于 2013-02-27T03:09:34.247 に答える
1

N 項目のリストから N 長の順列を再帰的に生成する一般的なアルゴリズムは次のとおりです。

リスト内の各要素 x について

要素 x を含まないリストのコピーを作成します。それを newList と呼ぶ newList のすべての順列を見つける

newList の各順列の先頭に要素 x を追加します

#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と同じように検索方法を使用できます。参照：の組み合わせ

于 2013-02-27T06:44:01.993 に答える