如何高效生成各部分元素数在m~n区间的k分集合划分？

需要实现一个功能：生成指定集合的k分集合划分，要求每个划分部分的元素数量处于m到n的区间内，且无需先计算所有可能的划分再筛选。已知more-itertools库的set_partitions函数可生成集合的k分划分，但无法直接满足上述元素数量范围的要求。

示例说明 #

1. 集合{'a','b','c','d'}的所有k=2分划分中，仅带*标记的划分满足各部分元素数在2-3之间：

['a', 'bcd']
['ab', 'cd']*
['b', 'acd']
['abc', 'd']
['bc', 'ad']*
['ac', 'bd']*
['c', 'abd']

2. 对于含9个元素的集合{'a','b','c','d','e','f','g','h','i'}，需找出所有划分为4个部分的结果，每个部分元素数需大于1且小于4（即2≤元素数≤3），符合要求的划分示例为['abc','de','fg','hi']和['ad','bc','efg','hi']，希望获取所有此类划分。

核心思路是逐步构建符合元素数量要求的子集，避免生成无效划分，以下是具体实现方案：

1. 先做可行性校验 #

生成前先判断是否存在符合条件的划分：

• 设集合总元素数为total，需满足：k*m ≤ total ≤ k*n
• 比如9个元素分4部分、每部分2-3个：4*2=8 ≤9 ≤4*3=12，符合条件，可行。

不满足则直接返回空迭代器，避免无效计算。

2. 递归生成符合约束的划分 #

编写递归生成器，每次从剩余元素中选出符合数量要求的子集，再递归处理剩余元素，直到分成k个部分：

from itertools import combinations

def constrained_set_partitions(elements, k, m, n):
    elements = list(elements)
    total = len(elements)
    # 可行性检查
    if not (k*m <= total <= k*n):
        return
    if k == 1:
        if m <= total <= n:
            yield [elements]
        return
    # 第一个子集的最大可能大小：不能超过n，且剩余元素要够分给k-1个每个至少m个的子集
    max_first_size = min(n, total - (k-1)*m)
    for size in range(m, max_first_size + 1):
        # 生成所有size大小的子集
        for subset in combinations(elements, size):
            subset = list(subset)
            remaining = [x for x in elements if x not in subset]
            # 递归生成剩余元素的k-1分划分
            for rest_partition in constrained_set_partitions(remaining, k-1, m, n):
                yield [subset] + rest_partition

3. 去重处理（可选） #

上述方法会生成顺序不同但实质相同的划分（比如[['ab','cd'], ['cd','ab']]），如果需要去重，可将每个划分的子集排序后存入集合去重：

def unique_constrained_partitions(elements, k, m, n):
    seen = set()
    for partition in constrained_set_partitions(elements, k, m, n):
        # 对每个子集、整个划分分别排序，转成可哈希的元组存入集合
        sorted_part = tuple(sorted(tuple(sorted(subset)) for subset in partition))
        if sorted_part not in seen:
            seen.add(sorted_part)
            # 转回列表格式返回
            yield [list(sub) for sub in sorted_part]

4. 示例验证 #

用第一个例子测试：

elements = {'a','b','c','d'}
for p in unique_constrained_partitions(elements, 2, 2, 3):
    print(p)

输出与示例中带*的结果一致：

[['a', 'b'], ['c', 'd']]
[['a', 'c'], ['b', 'd']]
[['a', 'd'], ['b', 'c']]

效率优势 #

直接使用set_partitions后筛选会生成大量无效划分（比如9个元素分4部分，总共有1401种k分划分，但符合条件的仅占一部分），而本方法直接跳过不符合元素数量要求的子集，大幅减少计算量，效率更高。

内容的提问来源于stack exchange，提问作者Ramon Masià