python - 如何从所有排列生成所有可能的组合？

Question

我有一个 Python 中 K 元素的所有排列列表，如下所示:

import itertools
perms = list(itertools.permutations(range(K), K))

我想生成这些排列 perms 所有可能组合的矩阵(或列表)M。此矩阵(或列表)的每个元素的大小为 N。我该怎么做？

例如，对于 K=2，我会得到 perms=[(0, 1), (1, 0)]。对于 N=3，我想要:

M = [ [(0, 1), (0, 1), (0, 1)],
      [(0, 1), (0, 1), (1, 0)],
      [(0, 1), (1, 0), (0, 1)],
      [(0, 1), (1, 0), (1, 0)],
      [(1, 0), (0, 1), (0, 1)],
      [(1, 0), (0, 1), (1, 0)],
      [(1, 0), (1, 0), (0, 1)],
      [(1, 0), (1, 0), (1, 0)] ]

M 是一个包含 8 个列表的列表。每个列表的大小为 N=3 并包含来自 perms 的元素。

对于N=2，我想要:

M = [ [(0, 1), (0, 1)],
      [(0, 1), (1, 0)],
      [(1, 0), (0, 1)],
      [(1, 0), (1, 0)] ]

对于 N=1，我希望:

M = [ [(0, 1), (1, 0)] ] = perms

我不知道我是否正确地表述了我的问题(我认为它可以比这更清楚地重新表述)。

Answer 1

您可以使用 itertools 中的 product。

from itertools import permutations, product

perms = permutations(range(2))
cartesian_tuples = product(perms, repeat=3)

# (((0, 1), (0, 1), (0, 1)),
#  ((0, 1), (0, 1), (1, 0)),
#  ((0, 1), (1, 0), (0, 1)),
#  ((0, 1), (1, 0), (1, 0)),
#  ((1, 0), (0, 1), (0, 1)),
#  ((1, 0), (0, 1), (1, 0)),
#  ((1, 0), (1, 0), (0, 1)),
#  ((1, 0), (1, 0), (1, 0)))

如果您需要多次迭代任何内容，您可以手动将各个部分转换为列表。当前结构由生成器组成，生成器将在一次迭代后耗尽，无法再次使用。如果你想要嵌套列表:

cartesian_tuples = map(list, list(product(perms, repeat=3)))

# [[(0, 1), (0, 1), (0, 1)],
#  [(0, 1), (0, 1), (1, 0)],
#  [(0, 1), (1, 0), (0, 1)],
#  [(0, 1), (1, 0), (1, 0)],
#  [(1, 0), (0, 1), (0, 1)],
#  [(1, 0), (0, 1), (1, 0)],
#  [(1, 0), (1, 0), (0, 1)],
#  [(1, 0), (1, 0), (1, 0)]]

在 Python 3.X 中，您必须将其包装在另一个 列表调用中，因为map(...) 返回一个map对象。

cartesian_tuples = list(map(list, list(product(perms, repeat=3))))

或者，您可以避免所有这些废话并使用列表理解。

cartesian_tuples = [[perm for perm in prod] for prod in product(perms, repeat=3)]

但每次需要时都创建一个新的迭代器可能会更好。

def product_of_permutations(n, k):
    return product(permutations(range(k)), repeat=n)