优化Python代码实现字母到盒子的分配，支持空盒、无重复字母

优化思路 #

你之前的方案性能差的核心原因是生成了大量无效候选后再做过滤，绝大多数计算资源都被浪费了。我们可以换一个维度思考问题：直接给每个字母分配归宿，每个字母要么不放入任何盒子，要么放入指定编号的盒子，所有生成的结果天然符合规则，完全不需要过滤，性能可以提升几个数量级。
对于你提到的最多6个盒子、6个字母的场景，这个方案的总计算量只有7^6 = 117649次，毫秒级就能跑完，远低于2分钟的要求。

实现代码 #

import itertools

def generate_valid_assignments(letters: list, n_boxes: int):
    """
    生成所有合法的字母分配方案
    :param letters: 待分配的字母列表
    :param n_boxes: 盒子数量
    :return: 每个元素是一个元组，对应每个盒子中的字母元组，空盒子对应空元组
    """
    # 每个字母的可选归宿：-1代表不放入任何盒子，0~n_boxes-1对应盒子索引
    all_choices = itertools.product(range(-1, n_boxes), repeat=len(letters))
    for choice in all_choices:
        boxes = [[] for _ in range(n_boxes)]
        for letter, box_idx in zip(letters, choice):
            if box_idx != -1:
                boxes[box_idx].append(letter)
        # 转成不可变的元组方便后续使用，sorted保证盒子内字母顺序统一
        yield tuple(tuple(sorted(box)) for box in boxes)

# 测试示例
if __name__ == "__main__":
    letters = ["A", "B", "C"]
    n_boxes = 2
    for idx, assignment in enumerate(generate_valid_assignments(letters, n_boxes), 1):
        print(f"方案{idx}: {assignment}")

方案验证 #

• 每个盒子可以是空、单个字母、多个字母组合：符合要求
• 所有字母最多出现一次，无重复：符合要求
• 盒子是有序的，不同盒子放相同字母会被识别为不同方案：和你原有代码的逻辑一致
  如果需要调整输出格式，只需要修改最后yield部分的转换逻辑即可。

内容的提问来源于stack exchange，提问作者Miguel Bordalo