我想通過遞歸得到每個列表元素的排列

我想要得到列表元素的每個排列組合。我試圖通過在兩個列表之間混洗這些元素並檢查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。

來源

2012-10-28 pawel

你的代碼不編譯（前見LU在您置換功能的尾巴）。另外，您可能想要反思遞歸算法的一個關鍵屬性：*使用堆棧保存遞歸狀態*，以及您可能會做錯的事情導致失敗。 – WhozCraig

我忘了更改參數名稱，現在它在VS2010中編譯：] – pawel

Craig是正確的... 1>。\ test.cpp（31）：錯誤C2065：'LU'：未聲明的標識符 – Caribou

用於遞歸從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; 
}

產生下面的輸出中，0..3所有排列：

來源

2012-10-28 22:48:30 WhozCraig

哇，太棒了！謝謝！：） – pawel

我想通過遞歸得到每個列表元素的排列

回答

相關問題