N ++的C++算法！排序

我有一個N項列表，我想知道如何通過列表循環來獲取每個組合。沒有雙打，所以我需要得到所有N！排序。額外的內存是沒有問題的，我試圖想到最簡單的算法，但我遇到了麻煩。N ++的C++算法！排序

來源

2010-01-26 Stuart

它是組合還是置換？ – sud03r 2010-01-26 19:19:05

另請參閱http://stackoverflow.com/questions/352203/generating-permutations-lazily/ – ShreevatsaR 2010-07-13 13:08:53

參見std::next_permutation

來源

2010-01-26 19:19:19

兩種不同算法的解釋良好的通話（可以這麼說）。儘管公平，OP確實要求最簡單的*算法*。 – 2010-01-27 02:22:21

C++ STL具有next_permutation用於此目的。

來源

2010-01-26 19:21:04 sud03r

擴大別人的答案，這裏是性病的例子::使用遞歸從cplusplus.com

#include <iostream> 
#include <algorithm> 
using namespace std; 

void outputArray(int* array, int size) 
{ 
    for (int i = 0; i < size; ++i) { cout << array[i] << " "; } 
} 

int main() 
{ 
    int myints[] = { 1, 2, 3, 4, 5 }; 
    const int size = sizeof(myints); 

    cout << "The 5! possible permutations with 5 elements:\n"; 

    sort (myints, myints + size); 

    bool hasMorePermutations = true; 
    do 
    { 
    outputArray(myints, size); 
    hasMorePermutations = next_permutation(myints, myints + size); 
    } 
    while (hasMorePermutations); 

    return 0; 
}

來源

2010-01-26 19:36:21 Bill

+1提供了一個例子。 – 2010-01-26 19:59:28

'bool'變量中似乎沒有任何一點。你可以'做{...} while（std :: next_permutation（...））;' – 2010-01-26 22:03:20

@Charles：這是真的，我可以做到這一點。出於教學目的，我從中取出next_permutation，因爲這是代碼的重點。 – Bill 2010-01-26 22:18:54

簡單的算法調整next_permutation：

僞

getPermutations(CurItemList , CurPermList) 

if CurItemList.isempty() 
    return CurPermList 
else 
    Permutations = {} 

    for i = 1 to CurItemList.size() 
     CurPermList.addLast(CurItemList.get(i)) 

     NextItemList = CurItemList.copy() 
     NextItemList.remove(i) 

     Permutations.add(getPermutations(NextItemList, CurPermList)) 

     CurPermList.removeLast() 


return Permutations 

// To make it look better 
Permutations(ItemList) 
    return getPermutations(ItemList, {})

我沒有測試它，但應該工作。也許它不是最聰明的做法，但它是一個簡單的方法。如果有什麼不對，請讓我知道！

來源

2010-01-26 20:36:05 George

嘗試使用固定數量的可能元素遞歸地構建一組組合。所有可能組合的集合將是1個元素，2個元素，...到N個元素的組合的集合。

然後你可以單獨攻擊每個固定大小的組合。

來源

2010-01-26 22:00:49 MSN

N ++的C++算法！排序

回答

相關問題