c++ - 我想通过递归获得列表元素的每一个排列

Question

我想获得列表元素的每一个排列。我试图通过在两个列表之间混洗这些元素并检查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 5和5 4 3 2 1。

score 3 · Accepted Answer

从 N 项列表递归生成 N 长度排列的通用算法是：

对于列表中的每个元素 x

复制没有元素 x 的列表；称它为新列表
找到 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;
}

产生以下输出，所有排列均为 0..3：

c++ - 我想通过递归获得列表元素的每一个排列

1 回答 1

Related

Reference