编写Python代码按规则拆分分组为子组（含例外限制）

需求说明 #

编写Python代码，将包含多行的分组按特定规则拆分为子组：

• 每行结构为 [[禁止行号列表], [允许行号列表], 当前行号]
• 每行仅能加入所有成员行号都在自身允许列表内的子组
• 子组内不能包含自身禁止列表中的任何行号

示例1 #

输入Group_A #

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

输出 #

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

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

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

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

规则示例说明 #

以第一行[[2, 3, 5, 6, 8], [1, 4, 7, 9], 0]为例：

• 0为当前行的行号
• [2,3,5,6,8]是当前行禁止加入的子组包含的行号（子组内不能有这些行）
• [1,4,7,9]是当前行可加入的子组包含的行号（子组内所有行必须属于该列表）

示例2 #

输入Group_B #

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

输出 #

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

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

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

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

实现代码 #

def split_groups(original_group):
    # 建立行号到行数据的映射
    line_map = {line[2]: line for line in original_group}
    # 记录已处理的行号
    processed = set()
    groups = []

    # 构建图：节点为行号，边表示两行可共存于同一子组
    graph = {}
    for num1 in line_map:
        graph[num1] = []
        line1 = line_map[num1]
        allowed1 = set(line1[1]) | {num1}
        forbidden1 = set(line1[0])
        for num2 in line_map:
            if num1 == num2:
                continue
            line2 = line_map[num2]
            allowed2 = set(line2[1]) | {num2}
            forbidden2 = set(line2[0])
            # 双向满足条件：互相在对方允许列表，且不在对方禁止列表
            if num2 in allowed1 and num2 not in forbidden1 and num1 in allowed2 and num1 not in forbidden2:
                graph[num1].append(num2)

    # Bron–Kerbosch算法找所有最大团
    def bronkkerbosch(R, P, X, cliques):
        if not P and not X:
            cliques.append(R.copy())
            return
        for v in list(P):
            bronkkerbosch(R + [v], [u for u in P if u in graph[v]], [u for u in X if u in graph[v]], cliques)
            P.remove(v)
            X.append(v)

    # 遍历所有未处理节点，生成最大团
    unvisited = set(line_map.keys())
    while unvisited:
        start_node = unvisited.pop()
        cliques = []
        bronkkerbosch([start_node], [u for u in unvisited if u in graph[start_node]], [], cliques)
        # 取最大的团（可能有多个相同大小的，这里取第一个）
        if cliques:
            max_clique = max(cliques, key=len)
            groups.append([line_map[num] for num in max_clique])
            # 标记团内节点为已处理
            processed.update(max_clique)
            unvisited -= processed

    # 格式化输出结果
    for idx, group in enumerate(groups, 1):
        print(f"Group_{idx} = [")
        for line in group:
            print(f"    {line},")
        print("]")
        print()

# 测试示例1
print("=== 示例1输出 ===")
Group_A = [
    [[2, 3, 5, 6, 8], [1, 4, 7, 9], 0],
    [[3, 4, 7, 8, 9], [0, 2, 5, 6], 1],
    [[0, 3, 7, 8, 9], [1, 4, 5, 6], 2],
    [[0, 1, 4, 7, 9], [2, 5, 6, 8], 3],
    [[1, 5, 6, 8, 9], [0, 2, 3, 7], 4],
    [[0, 2, 4, 7, 9], [1, 3, 6, 8], 5],
    [[0, 4, 7, 8, 9], [1, 2, 3, 5], 6],
    [[2, 3, 5, 6, 8], [0, 1, 4, 9], 7],
    [[0, 2, 4, 7, 9], [1, 3, 5, 6], 8],
    [[2, 3, 4, 6, 8], [0, 1, 5, 7], 9]
]
split_groups(Group_A)

# 测试示例2
print("=== 示例2输出 ===")
Group_B = [
    [[1, 3, 6, 7, 9], [2, 4, 5, 8], 0],
    [[0, 2, 4, 5, 8], [3, 6, 7, 9], 1],
    [[0, 1, 4, 7, 8], [3, 5, 6, 9], 2],
    [[0, 1, 4, 5, 8], [2, 6, 7, 9], 3],
    [[2, 3, 7, 8, 9], [0, 1, 5, 6], 4],
    [[1, 3, 6, 7, 9], [0, 2, 4, 8], 5],
    [[0, 1, 5, 7, 8], [2, 3, 4, 9], 6],
    [[0, 4, 5, 6, 8], [1, 2, 3, 9], 7],
    [[1, 4, 6, 7, 9], [0, 2, 3, 5], 8],
    [[0, 4, 5, 7, 8], [1, 2, 3, 6], 9]
]
split_groups(Group_B)

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