1

我正在尝试从列表中查找与列表大小相同或小于列表的所有排列。

例如：

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

这是我目前在 python 中的迭代代码。我不确定它目前的效率如何。

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，但伪代码也会对我有很大帮助。任何帮助，将不胜感激。提前致谢！

4

3 回答 3

4

以下应该有效：

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-06T21:29:16.143 回答
0

也许迭代所有可能大小的列表的所有排列。澄清：

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-06T21:29:10.213 回答
-1

我很确定你的permutations.add()andcurSet.add()和fullSet.add()调用会导致你的例行程序很快停止。如果您不断更改数组的大小，分配的内存将“空间不足”并且必须找到新位置。这意味着整个数组都会被复制。然后你添加另一个元素 - 冲洗并重复。

您需要计算所需元素的数量，并为此预先分配空间。因此，如果您有 5 个元素，则需要为最终结果分配 ( 5! + 5*4! + 10*3! + 10*2! + 5 ) x 5 个元素，而为中间结果分配更少的元素。然后你填充这些数组，而不用改变内存块；这将使事情变得更快。

于 2013-03-06T21:19:12.097 回答