从给定列表生成大小为 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

有itertools.combinations_with_replacement(). [New in 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)]

Answer 2

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

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)

或者，如果您需要它来处理任何 sequence，而不仅仅是列表，您可以使用

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

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

Generate permutations of size n from given list, where each permutations must contain all of the original values, possibly repeated

python

permutation

itertools