c++ - 再帰を介してリスト要素のすべての順列を取得したい

Question

リストの要素のすべての順列を取得したい。これらの要素を2つのリスト間でシャッフルし、の繰り返しをチェックすることでそれをやろうとしていますlist2。

しかし、何かが間違っています。私の問題を適切に解決するのを手伝ってもらえますか?

void iterlist(list<int>& Lit)
{
    list<int>::iterator it;

    for (it=Lit.begin(); it!=Lit.end(); it++)
        cout << " " << *it;

    cout << endl;
}

void permutations(list<int>& L1, list<int>& L2)
{
    L2.push_back(L1.front());
    L1.pop_front();

    if(!L1.empty())
    {
        permutations(L1, L2);
    }

    L1.push_back(L2.back());
    L2.pop_back();

    iterlist(L2);
}

の要素についてテストしていましたが、得られる順列はとL1 = 1,2,3,4,5のみです。1 2 3 4 55 4 3 2 1

score 3 · Accepted Answer

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

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

要素 x を含まないリストのコピーを作成します。それをnewListと呼ぶ
newList のすべての順列を検索します (これが再帰です)
newList の各順列の先頭に要素 x を追加します

これを行う方法は他にもありますが、再帰を学んでいる人にとって頭を包み込むのが最も簡単であると一貫してわかっている方法です。あなたが使用しているように見える方法は、アルゴリズムの反復ループ部分を2番目のリストに格納することを含みます. -疑いがやがて発見されます）。

以下は、一般的なアルゴリズムを示しています (特に効率的ではありませんが、そこから一般的なアイデアを得ることができます)。

#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;
}

次の出力を生成します。すべての順列は 0..3 です。

c++ - 再帰を介してリスト要素のすべての順列を取得したい

1 に答える 1

Related

Reference