Steiner系统：构建无重复、无余数的独特组合算法

def valid_combos(m, n):
    """
    检查给定m和n是否满足Steiner系统S(2, n, m)的必要存在条件，
    并返回所需组合的数量。
    """
    num_pairs_total = m * (m - 1) // 2 # 总共可能的两两配对数 C(m, 2)
    num_pairs_per_group = n * (n - 1) // 2 # 每组中的两两配对数 C(n, 2)

    if n <= 1 or m <= 1: # n或m小于等于1没有意义
        return False
    if (m - 1) % (n - 1) != 0: # 条件1
        return False
    if num_pairs_total % num_pairs_per_group != 0: # 条件2
        return False

    # 如果满足条件，计算所需的组数
    return num_pairs_total // num_pairs_per_group

# 示例
print(f"valid_combos(9, 3): {valid_combos(9, 3)}") # 输出 12
print(f"valid_combos(6, 3): {valid_combos(6, 3)}") # 输出 False

import random

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 item in id_list:
            if item in self.comparisons:
                self.comparisons.remove(item)

        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 item in id_list:
                if item in self.comparisons:
                    self.comparisons.remove(item)
            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

# 设定m和n的值
m = 9
n = 3

# 创建id对象列表
ids_master = get_ids(m)
ids = ids_master.copy()

comparisons = [] # 存储已成功生成的组合
invalid = []     # 存储导致死胡同的无效组合（用于剪枝）

# 获取所需的组合数量
combos_required = valid_combos(m, n)
if not combos_required:
    print(f"对于 m={m}, n={n}，不存在有效的Steiner系统S(2, n, m)。")
else:
    print(f"对于 m={m}, n={n}，需要 {combos_required} 个组合。")

    while len(comparisons) < combos_required:
        temp_group = [] # 临时存储当前正在构建的组

        try:
            # 优先处理第一个对象，确保其被充分利用
            if len(comparisons) < (m - 1) / (n - 1): # 第一个对象需要参与的组数
                if not temp_group: # 如果是组的第一个元素，固定为ids[0]
                    temp_group.append(ids[0])
                else: # 否则从剩余对象中随机选择
                    # 从除了ids[0]之外的ids中随机选择
                    # 注意：这里ids[1:]应该过滤掉已经在temp_group中的元素
                    available_ids = [obj for obj in ids[1:] if obj not in temp_group]
                    if not available_ids:
                        raise Exception("没有可用的ID来完成当前组。")

                    id_a = random.choice(available_ids)

                    # 检查id_a是否已与temp_group中的任何元素配对
                    is_valid_candidate = True
                    for id_b in temp_group:
                        if id_b.name in id_a.comparisons or id_b.name == id_a.name:
                            is_valid_candidate = False
                            break

                    if is_valid_candidate:
                        temp_group.append(id_a)
                    else:
                        # 如果随机选择的id_a无效，尝试其他id
                        # 简单地跳过当前循环，让while len(temp_group) < n 再次尝试
                        continue 
            else: # 对于后续的组，从ids列表中按顺序选择
                pos = 0 # 遍历ids列表的索引
                while len(temp_group) < n: # 继续构建组直到达到n个元素
                    if pos >= len(ids): # 如果遍历完所有ids仍未完成组，说明当前路径有问题
                        raise Exception("无法找到足够的ID来完成当前组。")

                    id_a = ids[pos]

                    # 检查id_a是否已在temp_group中
                    if id_a in temp_group:
                        pos += 1
                        continue

                    # 检查id_a是否已与temp_group中的任何元素配对
                    counter = 0
                    for id_b in temp_group:
                        if id_b.name in id_a.comparisons or id_b.name == id_a.name:
                            counter += 1
                            break # 发现冲突，无需继续检查

                    # 检查id_a是否已与所有其他m-1个对象配对（仅当它是组的第一个元素时需要此检查）
                    # 实际上，这个条件在这里可能过于严格，因为它阻止了id_a继续参与新的组
                    # 更好的做法是，如果id_a的配对数达到m-1，则它不能再作为新组的成员
                    # 但在这里，我们是构建一个组，只要它能与组内其他成员形成新的有效对即可
                    # if len(id_a.comparisons) == m - 1:
                    #     counter += 1 # 标记为无效

                    # 检查当前组(temp_group + id_a)是否是已知的无效组合
                    if counter == 0:
                        potential_group = temp_group.copy()
                        potential_group.append(id_a)
                        potential_group_names = sorted([x.name for x in potential_group])

                        for iv_names in invalid: # invalid存储的是name列表
                            if potential_group_names == iv_names:
                                counter += 1 # 标记为无效
                                break

                    if counter == 0:
                        temp_group.append(id_a)
                    pos += 1

        except Exception as e:
            # print(f"发生异常或无法完成组：{e}。开始回溯。")
            # 清空当前临时组
            temp_group.clear()

            # 确定要回溯（移除）多少个已生成的组合
            # 这里的逻辑比较复杂，目标是移除导致当前死胡同的最近一组或多组
            # 简单起见，可以尝试移除最后一个生成的组合，或者根据启发式判断

            # 记录导致问题的组合
            if comparisons:
                last_comparison = comparisons[-1]
                last_comparison_names = sorted([x.name for x in last_comparison])
                if last_comparison_names not in invalid: # 避免重复添加
                    invalid.append(last_comparison_names)

            # 回溯：移除最近的几个组合
            # 具体的移除数量需要根据实际情况调整，这里只是一个示例
            num_to_remove = 1 # 默认回溯一步
            if len(comparisons) > 0:
                # 尝试移除最后一个组合
                comparisons.pop() 

            # 重置所有id的比较记录
            for obj_id in ids_master:
                obj_id.update_comparisons([], mode='reset')

            # 重新构建已成功组合的比较记录
            for comp_group in comparisons:
                names = [x.name for x in comp_group]
                for obj_id in comp_group: # comp_group中的是id对象
                    obj_id.update_comparisons(names, mode='add')

            continue # 继续外层while循环，尝试重新生成组合

        # 如果成功构建了一个完整的组
        if len(temp_group) == n:
            comparisons.append(temp_group)

            # 更新所有相关id的比较记录
            current_group_names = sorted([x.name for x in temp_group])
            for obj_id in temp_group:
                obj_id.update_comparisons(current_group_names, mode='add')

    # 提取所有组合的名称
    final_comparison_names = []
    for comp_group in comparisons:
        final_comparison_names.append(sorted([x.name for x in comp_group]))

    print("\n生成的组合：")
    for group in final_comparison_names:
        print(group)

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

[[1, 8, 4], 
[1, 3, 2], 
[1, 9,