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。

Answer 1

从 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 的所有排列:

 3 2 1 0
 3 2 0 1
 3 1 2 0
 3 1 0 2
 3 0 2 1
 3 0 1 2
 2 3 1 0
 2 3 0 1
 2 1 3 0
 2 1 0 3
 2 0 3 1
 2 0 1 3
 1 3 2 0
 1 3 0 2
 1 2 3 0
 1 2 0 3
 1 0 3 2
 1 0 2 3
 0 3 2 1
 0 3 1 2
 0 2 3 1
 0 2 1 3
 0 1 3 2
 0 1 2 3