从给定列表中生成大小为n的排列，其中每个排列必须包含所有原始值，可能重复

Question

我试图创建一个小脚本，该脚本将接受元素列表并创建其内容的所有可能排列，而所有这些排列可能都有重复，大小必须为n，并包含所有原始值。我试着使用itertools库，但它们没有任何用处。我能做些简单的事情来实现这一点吗？

以下是列表[0,1,2]和n=3:的示例

[0,1,2]
[0,2,1]
[1,0,2]
[2,0,1]
[1,2,0]
[2,1,0]

对于n=4，输出中也将允许类似[0,1,1,2]的内容。

Answer 1

您描述的行为可以通过以下函数实现：

def perms_with_duplicates(lst: list, n: int) -> Iterator:
"""
Generate permutations of ``lst`` with length ``n``. 
If ``n`` is greater than the length of ``lst``, then the
resulting permutations will include duplicate elements 
from ``lst``. All of the original elements of ``lst``
are guaranteed to appear in each output permutation.
"""

# Number of duplicate entries that the permutations can include.
num_dupl = max(n - len(lst) + 1, 1)

return itertools.permutations(lst * num_dupl, n)

或者，如果你需要在任何序列上工作，而不仅仅是列表，你可以使用

def perms_with_duplicates(seq: Sequence, n: int) -> Iterator:
"""
Generate permutations of ``seq`` with length ``n``. 
If ``n`` is greater than the length of `seq`, then the
resulting permutations will include duplicate elements 
from ``seq``. All of the original elements of ``seq``
are guaranteed to appear in each output permutation.
"""

# Number of duplicate entries that the permutations can include.
num_dupl = max(n - len(seq) + 1, 1)
it_dupl =  itertools.chain.from_iterable(
itertools.repeat(seq, num_dupl)
)

return itertools.permutations(it_dupl, n)

两个函数的行为如下。注意，对于小于或等于输入序列长度的n，函数的行为与itertools.permutations完全相同。

>>> l = [0, 1, 2]
>>> list(perms_with_duplicates(l, 3))                                                                                                
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
>>> len(list(perms_with_duplicates(l, 4)))
360
>>> list(perms_with_duplicates(l, 4))                                                                                                
[(0, 1, 2, 0),
(0, 1, 2, 1),
(0, 1, 2, 2),
(0, 1, 0, 2),
(0, 1, 0, 1),
...
(1, 2, 1, 0),
(1, 2, 1, 0),
(1, 2, 1, 2),
(1, 2, 0, 0),
(1, 2, 0, 1),
...
(2, 1, 0, 2)]

Answer 2

存在itertools.combinations_with_replacement()。【3.1新增】

如果序列长度n等于唯一元素的数量，就像在你的例子中一样，那么通常不可能有重复，所以这将减少到itertools.permutations()

否则，对于一般情况，使用列表理解来过滤itertools.combinations_with_replacement():的原始输出

from itertools import combinations_with_replacement
elems = [0,1,1,2]
[comb for comb in combinations_with_replacement(elems, 4) if all(el in comb for el in elems)]
[(0, 0, 1, 2), (0, 0, 1, 2), (0, 1, 1, 2), (0, 1, 1, 2), (0, 1, 2, 2), (0, 1, 1, 2), (0, 1, 2, 2)]