枚举一个列表的所有排序排列组合。

Question

假设一个列表 A = ["Foo", "Buzz", "Fizz", "Bar"].当我们把它分类 首字 附带 稳定的 排序算法，我们得到

>>> sorted(A, key=lambda x: x[0])
['Buzz', 'Bar', 'Foo', 'Fizz']

但是，一个 杌陧 排序可能会产生4种不同的结果。

['Bar', 'Buzz', 'Fizz', 'Foo']
['Bar', 'Buzz', 'Foo', 'Fizz']
['Buzz', 'Bar', 'Fizz', 'Foo']
['Buzz', 'Bar', 'Foo', 'Fizz']

如何生成任意列表中所有不稳定排序的排列组合?

Answer 1

from collections import defaultdict
from itertools import permutations, product, chain

# Some data.
xs = ['foo', 'buzz', 'fizz', 'bar', 'blort', 'doh', 'duh']

# When you sort, you use a function to create the sort keys.
# For example, sorting by first letter.
def firstletter(x):
    return x[0]

# Create a data structure mapping each unique sort key to all
# corresponding values in the original data.
#   'f': ['foo', 'fizz']
#   'b': ['buzz', 'bar', 'blort']
#   'd': ['doh', 'duh']
k2xs = defaultdict(list)
for x in xs:
    k2xs[firstletter(x)].append(x)

# For each key, get the possible permutations.
perms = [
    list(permutations(k2xs[k]))
    for k in sorted(k2xs)
]

# We need the Cartesian product of those permutations.
sorts_grouped = list(product(*perms))

# And we want it flattened.
sorts = [
    list(chain(*tups))         # Equivalent to [x for tup in tups for x in tup]
    for tups in sorts_grouped
]

# Check.
for ys in sorts:
    print(ys)

输出。

['buzz', 'bar', 'blort', 'doh', 'duh', 'foo', 'fizz']
['buzz', 'bar', 'blort', 'doh', 'duh', 'fizz', 'foo']
['buzz', 'bar', 'blort', 'duh', 'doh', 'foo', 'fizz']
['buzz', 'bar', 'blort', 'duh', 'doh', 'fizz', 'foo']
['buzz', 'blort', 'bar', 'doh', 'duh', 'foo', 'fizz']
['buzz', 'blort', 'bar', 'doh', 'duh', 'fizz', 'foo']
['buzz', 'blort', 'bar', 'duh', 'doh', 'foo', 'fizz']
['buzz', 'blort', 'bar', 'duh', 'doh', 'fizz', 'foo']
['bar', 'buzz', 'blort', 'doh', 'duh', 'foo', 'fizz']
['bar', 'buzz', 'blort', 'doh', 'duh', 'fizz', 'foo']
['bar', 'buzz', 'blort', 'duh', 'doh', 'foo', 'fizz']
['bar', 'buzz', 'blort', 'duh', 'doh', 'fizz', 'foo']
['bar', 'blort', 'buzz', 'doh', 'duh', 'foo', 'fizz']
['bar', 'blort', 'buzz', 'doh', 'duh', 'fizz', 'foo']
['bar', 'blort', 'buzz', 'duh', 'doh', 'foo', 'fizz']
['bar', 'blort', 'buzz', 'duh', 'doh', 'fizz', 'foo']
['blort', 'buzz', 'bar', 'doh', 'duh', 'foo', 'fizz']
['blort', 'buzz', 'bar', 'doh', 'duh', 'fizz', 'foo']
['blort', 'buzz', 'bar', 'duh', 'doh', 'foo', 'fizz']
['blort', 'buzz', 'bar', 'duh', 'doh', 'fizz', 'foo']
['blort', 'bar', 'buzz', 'doh', 'duh', 'foo', 'fizz']
['blort', 'bar', 'buzz', 'doh', 'duh', 'fizz', 'foo']
['blort', 'bar', 'buzz', 'duh', 'doh', 'foo', 'fizz']
['blort', 'bar', 'buzz', 'duh', 'doh', 'fizz', 'foo']

Answer 2

重构并略微优化 FMc的解决方案:

from itertools import permutations, product, chain, groupby

def sorted_permutations(iter, key=lambda x: x, reverse=False):
    # map each unique sort key to all
    # corresponding values in the original data
    key_groups = dict((k, tuple(v)) for k, v in
                      groupby(sorted(iter, key=key), key=key))

    # for each key, get the possible permutations
    perms = (
        permutations(key_groups[k])
        for k in sorted(key_groups, reverse=reverse)
    )

    # the Cartesian product of those permutations
    sorts_grouped = product(*perms)

    for parts in sorts_grouped:
        # flatten them
        yield list(chain(*parts))