python - 将 a 项的所有组合列出到大小为 c 的 b 组中

Question

我正在Python中寻找一种方法，将任意数量的项目拆分为任意数量的偶​​数组，并获取所有这些拆分的列表/数组。

例如，给定 12 个项目，有 5775 种方法将它们分为 3 组，每组 4 组。计算这不是问题，但我似乎找不到返回这些 5775 项的列表或数组的方法.我可以使用以下方法获得第一组:

import itertools
list(itertools.combinations(range(12), 4))

但是我怎样才能从中获得剩余的组呢？

a = 4、b = 2、c = 2 所需的输出为:

[[[1, 2], [3, 4]],
 [[1, 3], [2, 4]],
 [[1, 4], [2, 3]]]

对于a = 3、b = 3、c = 1:

[[[1], [2], [3]]]

Answer 1

您可以使用递归生成器，在每个级别或递归中计算(剩余)项目的所有组合。下一级递归仅接收当前级别中尚未使用的那些项目(剩余)。

为了防止组排序方面的重复，我们需要截断 it.combinations 的输出这样它就不会产生在之前迭代的剩余部分中出现过的组合。让n是项目数量和 g每组的大小。然后是 it.combinations 中的第一项是 (0, 1, ..., g-1) (就指数而言)。该项目(1, 2, ..., g)当当前项来自 it.combinations 时，将成为余数的一部分是 (0, g, g+1, ..., 2*g-1) (假设 n % g == 0 )。因此，我们需要截断 it.combinations 的输出这样第一个元素是固定的(上例中的 0 )。因为it.combinations按字典顺序生成项目，这涵盖了第一个 (n-1)! / (n-g)! / (g-1)!项( ! 表示阶乘)。

以下是一个示例实现:

import itertools as it
from math import factorial
from typing import Iterator, Sequence, Tuple, TypeVar


T = TypeVar('T')


def group_items(items: Sequence[T], group_size: int) -> Iterator[Tuple[Tuple[T, ...], ...]]:
    if len(items) % group_size != 0:
        raise ValueError(
            f'Number of items is not a multiple of the group size '
            f'({len(items)} and {group_size})'
        )
    elif len(items) == group_size:
        yield (tuple(items),)
    elif items:
        count, _r = divmod(
            factorial(len(items) - 1),
            factorial(len(items) - group_size) * factorial(group_size - 1)
        )
        assert _r == 0
        for group in it.islice(it.combinations(items, group_size), count):
            remainder = [x for x in items if x not in group]  # maintain order
            yield from (
                (group, *others)
                for others in group_items(remainder, group_size)
            )


result = list(group_items(range(12), 4))
print(len(result))

from pprint import pprint
pprint(result[:3])
pprint(result[-3:])

请注意，上面的示例使用 remainder = [x for x in items if x not in group]计算哪些项目应该进入下一级递归。如果您的团体规模很大，这可能会效率低下。相反，您也可以使用 set (如果您的项目是可哈希的)。另外，如果项目之间的相等比较( == )成本很高，那么最好使用索引而不是使用项目并计算 group 。和remainder从这些指数中。为了保持简单，我没有在上面的代码片段中包含这些方面，但如果您对细节感兴趣，我可以扩展我的答案。