如何有效地從大小爲n的列表中獲取大小爲{n，n-1，n-2，...}的所有排列組合？

我正在嘗試從列表中找到所有與列表大小相同或更小的排列。如何有效地從大小爲n的列表中獲取大小爲{n，n-1，n-2，...}的所有排列組合？

例如：

>>>allPermutations([a,b]) 
[[a,b], [b,a], [a], [b]]

這是迭代的代碼，我目前在蟒蛇。我不確定它目前的效率如何。

import itertools 

def getAllPossibleSubSchedules(seq): 
    fullSet = set() 
    curSet = set() 
    curSet.add(tuple(seq)) 
    for i in reversed(range(1, len(seq) + 1)): 
     permutations = set() 
     for curTuple in curSet: 
      permutationsList = list(itertools.permutations(curTuple, i)) 
      for permutation in permutationsList: 
       permutations.add(permutation) 
     curSet = set() 
     for permutation in permutations: 
      curSet.add(permutation) 
      fullSet.add(permutation) 
    return fullSet

我很肯定算法會產生總和n！從1 - > n排列，其增長速度非常快。到目前爲止，我已經創建了一個遞歸的方式來實現，因爲它執行了許多重複的操作，所以速度非常慢。我一直試圖通過迭代來實現，但我無法弄清楚如何限制重複操作。我使用python，但僞代碼也會幫助我很多。任何幫助，將不勝感激。提前致謝！

來源

2013-03-06 user1928755

這豈不是比找到一組給定的冪強硬？因爲這是一個與排序相似的問題。我只是出於好奇心問，因爲我認爲這就是他們稱之爲「NP完全」的問題。 – Mariano 2013-03-06 21:21:22

@Mariano誰是「他們」？簡而言之，（非完整）一個NP完全問題是一個問題，它可以解決另一個NP多完成問題，即多時翻譯時間。這與時間複雜性無關。 – kay 2013-03-06 21:26:05

「他們」是知道這件事的人，我不是其中的一員，這就是我問的原因。謝謝你的解釋。 – Mariano 2013-03-06 21:30:52

-1

我很確定你的permutations.add()和curSet.add()和fullSet.add()調用會導致你的例程非常快地停止爬行。如果您不斷更改數組的大小，則分配的內存將「空間不足」，並且必須找到新的位置。這意味着整個數組被複制。然後添加另一個元素 - 沖洗並重復。

您需要計算您需要的元素數量併爲其預先分配空間。因此，如果您有5個元素，則需要爲最終結果分配（5！+ 5 * 4！+ 10 * 3！+ 10 * 2！+ 5）x 5個元素 - 對於中間結果則要少一些。然後你填充這些數組，而不用混淆內存塊;它會使事情顯着加快。

來源

2013-03-06 21:19:12 Floris

也許遍歷所有可能大小的列表的所有排列。爲了澄清：

def all_permutations(input_list): 
    for i in xrange(len(input_list)): 
     sublist = input_list[:i] 
     for variant in permutations(sublist): 
      yield variant

來源

2013-03-06 21:29:10

下面應該工作：

from itertools import permutations 

def allPermutations(seq): 
    return (x for i in range(len(seq),0,-1) for x in permutations(seq, i))

例如：

>>> list(allPermutations('abc')) 
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('a',), ('b',), ('c',)]

來源

2013-03-06 21:29:16

如何有效地從大小爲n的列表中獲取大小爲{n，n-1，n-2，...}的所有排列組合？

回答

相關問題