python - 如何有效地从大小为 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

我非常确定该算法会产生 n 的总和!从 1 -> n 排列增长得相当快。到目前为止，我已经创建了一种递归方法来执行此操作，但速度非常慢，因为它执行了许多重复操作。我一直试图通过迭代来做到这一点，但我不知道如何限制重复操作。我正在使用 python，但伪代码也会对我有很大帮助。任何帮助，将不胜感激。提前致谢!

Answer 1

以下应该有效:

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