如何高效获取大小为n的列表中所有规模为{n, n-1, n-2, ... 1}的排列？

Question

我正在尝试从一个列表中找出所有的排列，这些排列的大小要和列表一样大或者更小。

举个例子：

>>>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

我很确定这个算法会产生从1到n的n!的总和的排列，这个数量增长得非常快。到目前为止，我已经创建了一种递归的方法来实现这个，但它非常慢，因为它做了很多重复的操作。我一直在尝试通过迭代来实现，但我不知道怎么限制重复的操作。我使用的是Python，但伪代码也会对我有很大帮助。任何帮助都非常感谢！提前谢谢！

Answer 1

我很确定你在调用 permutations.add()、curSet.add() 和 fullSet.add() 的时候，会让你的程序变得非常慢。如果你一直在改变数组的大小，内存就会“没有空间”了，这样就需要找到新的位置来存放数据。这就意味着整个数组需要被复制一次。然后你再添加一个元素，重复这个过程。

你需要先计算出需要多少个元素，然后提前分配好空间。比如说，如果你有5个元素，你需要为最终结果分配 (5! + 5*4! + 10*3! + 10*2! + 5) x 5 个元素的空间，而中间结果需要的空间会少一些。这样你就可以直接填充这些数组，而不是在内存中移动数据块，这样会让程序运行得快很多。

Answer 2

也许可以对所有可能大小的列表进行所有排列的遍历。为了更清楚：

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

Answer 3

下面的代码应该可以正常运行：

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',)]