具有重复的排序列表的有效排列
Efficient Permutation of a Sorted List with Repetitions
我有一个分配给等级的名字列表，通常有重复的等级。我想生成列表的所有排列，同时保持排序顺序。例如：
[Sam(17), Harry(17), Bob(5), Sally(5)]
会生成
Sam(17), Harry(17), Bob(5), Sally(5)
Sam(17), Harry(17), Sally(5), Bob(5)
Harry(17), Sam(17), Bob(5), Sally(5)
Harry(17), Sam(17), Sally(5), Bob(5)
基本上，对于每个不同的等级组，有 n！组合。在这种情况下，它将是 2！ * 2！。我无法找到一种有效的方法来对 8 个等级的 34 个名称的列表进行排列。
我 运行 内存不足，试图找到 2！ * 2！ * 4！ * 2！ * 2！ *8！ * 4！ * 10！不同的列表。
有什么有效的方法可以生成这个列表吗？ python 需要多少内存？
这是使用 groupby、permutations 和 product 的 itertools 解决方案。由于它主要使用生成器，因此内存应该不会太重。如果您不需要结果作为列表，但例如只想迭代它，内存需求实际上应该相当适中。
如果您需要该列表，您将需要用于该列表的内存，但仅此而已。
但恐怕仅凭您的数字，最终列表就太大而无法容纳在内存中。循环将永远持续下去。
>> import itertools, operator
>>>
>>> data = *zip('Peter Paul Mary Jack Jill'.split(), (17, 17, 17, 4, 4)),
>>> data
(('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4))
>>>
# group by rank
>>> groups = itertools.groupby(data, operator.itemgetter(1))
# extract the groups and generate all permutations of each of them
>>> permutations = map(itertools.permutations, map(operator.itemgetter(1), groups))
# form the cartesian product of the permutations, flatten out excess nesting
# convert inner generators to lists
>>> result = map(list, map(itertools.chain.from_iterable, itertools.product(*permutations)))
>>> for i in result:
... print(i)
...
[('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4)]
[('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jill', 4), ('Jack', 4)]
[('Peter', 17), ('Mary', 17), ('Paul', 17), ('Jack', 4), ('Jill', 4)]
[('Peter', 17), ('Mary', 17), ('Paul', 17), ('Jill', 4), ('Jack', 4)]
[('Paul', 17), ('Peter', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4)]
[('Paul', 17), ('Peter', 17), ('Mary', 17), ('Jill', 4), ('Jack', 4)]
[('Paul', 17), ('Mary', 17), ('Peter', 17), ('Jack', 4), ('Jill', 4)]
[('Paul', 17), ('Mary', 17), ('Peter', 17), ('Jill', 4), ('Jack', 4)]
[('Mary', 17), ('Peter', 17), ('Paul', 17), ('Jack', 4), ('Jill', 4)]
[('Mary', 17), ('Peter', 17), ('Paul', 17), ('Jill', 4), ('Jack', 4)]
[('Mary', 17), ('Paul', 17), ('Peter', 17), ('Jack', 4), ('Jill', 4)]
[('Mary', 17), ('Paul', 17), ('Peter', 17), ('Jill', 4), ('Jack', 4)]
我有一个分配给等级的名字列表，通常有重复的等级。我想生成列表的所有排列，同时保持排序顺序。例如：
[Sam(17), Harry(17), Bob(5), Sally(5)]
会生成
Sam(17), Harry(17), Bob(5), Sally(5)
Sam(17), Harry(17), Sally(5), Bob(5)
Harry(17), Sam(17), Bob(5), Sally(5)
Harry(17), Sam(17), Sally(5), Bob(5)
基本上，对于每个不同的等级组，有 n！组合。在这种情况下，它将是 2！ * 2！。我无法找到一种有效的方法来对 8 个等级的 34 个名称的列表进行排列。
我 运行 内存不足，试图找到 2！ * 2！ * 4！ * 2！ * 2！ *8！ * 4！ * 10！不同的列表。
有什么有效的方法可以生成这个列表吗？ python 需要多少内存？
这是使用 groupby、permutations 和 product 的 itertools 解决方案。由于它主要使用生成器，因此内存应该不会太重。如果您不需要结果作为列表，但例如只想迭代它，内存需求实际上应该相当适中。
如果您需要该列表，您将需要用于该列表的内存，但仅此而已。
但恐怕仅凭您的数字，最终列表就太大而无法容纳在内存中。循环将永远持续下去。
>> import itertools, operator
>>>
>>> data = *zip('Peter Paul Mary Jack Jill'.split(), (17, 17, 17, 4, 4)),
>>> data
(('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4))
>>>
# group by rank
>>> groups = itertools.groupby(data, operator.itemgetter(1))
# extract the groups and generate all permutations of each of them
>>> permutations = map(itertools.permutations, map(operator.itemgetter(1), groups))
# form the cartesian product of the permutations, flatten out excess nesting
# convert inner generators to lists
>>> result = map(list, map(itertools.chain.from_iterable, itertools.product(*permutations)))
>>> for i in result:
... print(i)
...
[('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4)]
[('Peter', 17), ('Paul', 17), ('Mary', 17), ('Jill', 4), ('Jack', 4)]
[('Peter', 17), ('Mary', 17), ('Paul', 17), ('Jack', 4), ('Jill', 4)]
[('Peter', 17), ('Mary', 17), ('Paul', 17), ('Jill', 4), ('Jack', 4)]
[('Paul', 17), ('Peter', 17), ('Mary', 17), ('Jack', 4), ('Jill', 4)]
[('Paul', 17), ('Peter', 17), ('Mary', 17), ('Jill', 4), ('Jack', 4)]
[('Paul', 17), ('Mary', 17), ('Peter', 17), ('Jack', 4), ('Jill', 4)]
[('Paul', 17), ('Mary', 17), ('Peter', 17), ('Jill', 4), ('Jack', 4)]
[('Mary', 17), ('Peter', 17), ('Paul', 17), ('Jack', 4), ('Jill', 4)]
[('Mary', 17), ('Peter', 17), ('Paul', 17), ('Jill', 4), ('Jack', 4)]
[('Mary', 17), ('Paul', 17), ('Peter', 17), ('Jack', 4), ('Jill', 4)]
[('Mary', 17), ('Paul', 17), ('Peter', 17), ('Jill', 4), ('Jack', 4)]