Python 如何将元素放入几个桶中

问题描述

我需要遍历所有可能的组合，将初始的可迭代元素放入多个桶中。

示例：将 ABCDEFG 放入长度为 3 和 2 的两个桶中 –>

[ABC, DE], [ABC, DF], [ABC, DG], [ABD, CE], [ABD, EF], ..., [CDE, FG]

每个桶中只能有不重复的组合（不考虑排列）。

编辑：桶很重要，因为 ABC, DE 和 ABD, CE 被认为是不同的组合（总共仍然是相同的5个元素，但在桶中分配不同）。而 ABC, DE 和 ACB, DE 被认为是相同的组合。

桶内元素的顺序变化不是不同的组合，而在桶之间移动元素则是不同的组合。

我想我应该使用 itertools.combinations() 的某种方式：

itertools.combinations('ABCDEFG', 3) --> ABC, ABD, ..., EFG

或与其他内容结合起来。

但是我在努力想出如何将输出进一步分布在不同长度的 多个桶 中。

解决方案

这里是一种可能的实现方式，它依靠“样本空间”的元素可以哈希。这假设元素落入哪个桶中很重要，所以特定的[ABC, DE]和[ABD, CE]被认为是两种不同的结果。

import itertools
from typing import Iterable, Iterator, TypeVar


_T = TypeVar("_T")


def two_bin_combs(
    iterable: Iterable[_T], b1: int, b2: int
) -> Iterator[tuple[tuple[_T, ...], tuple[_T, ...]]]:
    space = set(iterable)
    for left in itertools.combinations(space, b1):
        for right in itertools.combinations(space - set(left), b2):
            yield left, right

然后

sample_space = "ABCDEFG"
buckets = list(two_bin_combs(sample_space, 3, 2))

print(len(buckets))
print(buckets)

输出

210
[
    (('A', 'B', 'C'), ('E', 'D')),
    (('A', 'B', 'D'), ('C', 'E')),
    (('A', 'B', 'E'), ('C', 'D')), 
    (('A', 'C', 'D'), ('E', 'B')), 
    (('A', 'C', 'E'), ('D', 'B'))
    # ...
    (('C', 'F', 'G'), ('D', 'E')), 
    (('D', 'E', 'F'), ('G', 'C')), 
    (('D', 'E', 'G'), ('F', 'C')), 
    (('D', 'F', 'G'), ('C', 'E')), 
    (('E', 'F', 'G'), ('D', 'C')),
]

请注意输出顺序是不确定的，它取决于集合迭代顺序，可能会在每次运行时变化。

这种方法也可以推广到任意数量的容器：

def bin_combs(
    iterable: Iterable[_T], *bin_sizes: int
) -> Iterator[tuple[tuple[_T, ...], ...]]:

    total_space = frozenset(iterable)
    if len(total_space) < sum(bin_sizes):
        raise ValueError("total size of bins exceeds size of sample space")

    def _bin_combs(
        space: frozenset[_T], *bin_sizes: int
    ) -> Iterator[tuple[tuple[_T, ...], ...]]:

        if not bin_sizes:
            yield ()
            return

        curr_size, *remaining = bin_sizes

        for head in itertools.combinations(space, curr_size):
            for tail in _bin_combs(space - frozenset(head), *remaining):
                yield (head,) + tail

    return _bin_combs(total_space, *bin_sizes)