如何有效地从大小为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，...}的所有排列组合？

回答

相关问题