列出一組給定值的所有排列

Question

我有興趣對不同的技術/方法進行比較，這些技術/方法可用於生成給定集合的所有潛在排列。

Answer 1

您可以選擇性能，特定分佈和簡單性。我的意思是，你是否關心一些特定的順序，如詞典的輸出。

據我所知，效果最好的算法是Steinhaus algorithm。從某種意義上說，只有一個處理器指令是必要的才能生成一個排列（不包括打印它所需的指令並不總是需要），這對於乘法常數是最優的。

還有一個非常簡單的算法，它可以按字典順序生成排列，您可能可以自己重新創建一個遞歸過程，其性能爲O（n.log（n）.log（n ）），因此與通過任何其他方法生成列表並對其進行排序大致相同。

編輯：這裏是一個簡單的算法的僞代碼：

void permute(Element[] permutationPrefix, Set rest) 
{ 
    if (rest.IsEmpty) { 
     // permutationPrefix is now a full permutation 
     print(permutationPrefix); 
    } else { 
     foreach (element in rest) { 
      permutationPrefix.Append(element); 
      permute(permutationPrefix, rest.Minus(element)) 
      permutationPrefix.Length--; // cut away the last item 
     } 
    } 
} 

最初與空permutationPrefix和rest拿着全套稱之爲;如果這個集合是一個有序的數據結構，排列將按字典順序輸出。

請注意，我們正在複製和修改每個遞歸調用中的集合，這是整個算法中最昂貴的操作，可能與print方法一起使用。單套副本的成本是對數排列的總數n;並且因爲遞歸調用棧的深度也是對數的，所以下面是性能估計。

（此算法也適合改裝成一個很乖的隨機置換生成。）

Answer 2

這個問題已經（其實很多次）提出和回答：

Algorithm to generate all possible permutations of a list?

Permutations with a given integer

就我個人而言，我認爲Steinhaus算法正在過度思考問題：它並沒有比最天真的實現更快。最天真的實施

類似Java的僞代碼：

List<List<Element>> generateAllPermutations(List<Element> input) 
{ 
    List<Element> output = new ArrayList<Element>(); 
    if (input.size() == 0) 
     return output; 
    for (Element first : input) { 
     for (List<Element> sequence : generateAllPermutations(input - first)) 
      output.add(first + sequence); 
    } 
}