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++算法！排序

回答

相关问题