生成无重复无余数独特组合：Steiner 系统与回溯算法实践

[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[1, 8, 9]
[2, 4, 9]
[2, 5, 7]
[2, 6, 8]
[3, 4, 6]
[3, 7, 9]
[3, 5, 8]
[4, 7, 8]
[5, 6, 9]

def valid_combos(m, n):
    """
    计算 m 个对象，n 个一组的 Steiner 系统 S(2, n, m) 所需的组合数。
    同时检查 Steiner 系统 S(2, n, m) 的必要存在条件。
    """
    if n <= 1 or m <= 1:
        return False # 无效的 m 或 n 值

    # 条件一：(m-1) 必须能被 (n-1) 整除
    if (m - 1) % (n - 1) != 0:
        return False

    # 条件二：m*(m-1) 必须能被 n*(n-1) 整除
    # 这等价于 C(m, 2) / C(n, 2)
    if (m * (m - 1)) % (n * (n - 1)) != 0:
        return False

    # 如果条件满足，计算组合数
    return (m * (m - 1)) // (n * (n - 1))

class id:
    def __init__(self, name):
        self.name = name
        self.comparisons = [] # 存储已与该对象配对的其他对象的名称

    def update_comparisons(self, id_list, mode='add'):
        """
        更新该对象已配对的列表。
        mode='add': 添加新的配对。
        mode='del': 移除配对（用于回溯）。
        mode='reset': 清空所有配对。
        """
        # 移除重复项，确保列表唯一性
        for other_id_name in id_list:
            if other_id_name in self.comparisons:
                self.comparisons.remove(other_id_name)

        if mode == 'add':
            self.comparisons.extend(id_list)
            # 排序并移除自身，保持列表规范化
            self.comparisons.sort()
            if self.name in self.comparisons:
                self.comparisons.remove(self.name)
        elif mode == 'del':
            for other_id_name in id_list:
                if other_id_name in self.comparisons:
                    self.comparisons.remove(other_id_name)
            self.comparisons.sort()
        elif mode == 'reset':
            self.comparisons.clear()
        return self.comparisons

def get_ids(n):
    """创建 n 个 id 对象实例"""
    ids = []
    for i in range(1, n + 1):
        ids.append(id(i))
    return ids

import random

# 假设 m, n 已设定，ids_master, ids, get_ids, valid_combos 已定义
# m = 9
# n = 3
# ids_master = get_ids(m)
# ids = ids_master.copy()

comparisons = []       # 存储所有已生成的有效组合（id 对象列表）
comparison_names = []  # 存储所有已生成的有效组合（名称列表）
invalid = []           # 存储已尝试但被判定为无效的组合路径

combos_required = valid_combos(m, n) # 需要生成的总组合数

while len(comparisons) < combos_required:
    temp_group = [] # 当前正在构建的组合
    current_pos = 0 # 用于遍历 ids 列表

    # 内层循环：构建一个大小为 n 的组合
    while len(temp_group) < n:
        try:
            # 启发式：在生成最初几组时，可能选择第一个ID作为固定点，
            # 之后随机选择以增加探索性。
            # (m - 1) / (n - 1) 是每个元素需要出现的组合次数
            if len(comparisons) < (m - 1) / (n - 1):
                if len(temp_group) == 0:
                    # 如果是组的第一个元素，选择第一个ID
                    temp_group.append(ids[0])
                else:
                    # 否则，从剩余ID中随机选择一个
                    candidate_id = random.choice(ids[1:])
                    is_valid_candidate = True
                    for member_in_group in temp_group:
                        # 检查是否已配对或重复
                        if member_in_group.name in candidate_id.comparisons or \
                           member_in_group.name == candidate_id.name:
                            is_valid_candidate = False
                            break
                    if is_valid_candidate:
                        temp_group.append(candidate_id)
            else:
                # 正常情况：顺序选择 ID 并进行严格校验
                candidate_id = ids[current_pos]
                is_valid_candidate = True

                # 检查与 temp_group 中现有元素的配对情况
                for member_in_group in temp_group:
                    if member_in_group.name in candidate_id.comparisons or \
                       member_in_group.name == candidate_id.name:
                        is_valid_candidate = False
                        break

                # 检查当前 candidate_id 是否已与所有其他 (m-1) 个对象配对
                if len(candidate_id.comparisons) == m - 1:
                    is_valid_candidate = False

                # 进一步校验：避免生成已被标记为“无效”的组合
                if is_valid_candidate:
                    # 创建一个临时组名列表进行比较
                    v_check_names = [x.name for x in temp_group]
                    v_check_names.append(candidate_id.name)
                    v_check_names.sort() # 规范化顺序
                    for invalid_group_names in invalid_names: # invalid_names 需要在外部维护
                        if v_check_names == invalid_group_names:
                            is_valid_candidate = False
                            break

                if is_valid_candidate:
                    temp_group.append(candidate_id)

                current_pos += 1
                # 如果 current_pos 超出 ids 范围，说明无法找到有效元素，需要回溯
                if current_pos >= len(ids) and len(temp_group) < n:
                    raise Exception("无法找到下一个有效元素，需要回溯。")

        except Exception as e:
            # 发生异常，表示当前路径无法完成，需要回溯
            # 清空当前临时组
            temp_group.clear()

            # 回溯策略：识别并移除导致问题的最近组合
            num_to_remove = 0