从被折叠的损坏比赛结果数据中重建缺失的轮空(_)信息

核心逻辑说明 #

首先明确折叠规则：原始n行n列的结果中，每列对应一名选手，恰好有1个轮空标记_，折叠时直接删除每列的_就得到了n-1行的损坏数据。我们的还原目标是给每列插入恰好1个_，同时满足：

• 每行恰好有1个_（每场比赛恰好1人轮空）
• 每行去掉_后的排名是1~n-1的无重复排列
• 所有非_元素的顺序和损坏数据的顺序保持一致

完整实现代码 #

import numpy as np

collapsed_results = []
p = 0
solutions = []


def insert_bye(grid, row, column):
    for i in reversed(range(row, p)):
        if i == row:
            grid[i][column] = "_"
        else:
            grid[i][column] = grid[i - 1][column]
    return grid


def is_valid(grid, current_col):
    # 检查到current_col列为止是否存在非法重复排名
    for row in range(p):
        existed_nums = []
        for col in range(current_col + 1):
            val = grid[row][col]
            # 忽略轮空标记和未处理列的初始占位值
            if val != '_' and val != '0':
                if val in existed_nums:
                    return False
                existed_nums.append(val)
    return True


def solve(grid, col=0, used_rows=set()):
    # 所有列处理完成，找到有效解
    if col == p:
        solutions.append(grid.copy())
        return
    # 遍历所有未被占用的行尝试插入轮空
    for row in range(p):
        if row not in used_rows:
            new_grid = grid.copy()
            new_grid = insert_bye(new_grid, row, col)
            # 提前剪枝，仅合法状态继续递归
            if is_valid(new_grid, col):
                used_rows.add(row)
                solve(new_grid, col + 1, used_rows)
                # 回溯
                used_rows.remove(row)


if __name__ == "__main__":
    while True:
        try:
            line = input()
        except EOFError:
            break
        line = line.split(" ")
        collapsed_results.append(line)

    # 读取选手数量
    p = len(collapsed_results[0])
    # 扩展为p行p列的初始待处理数组
    collapsed_results.append(['0'] * p)
    collapsed_results = np.array(collapsed_results, dtype=str)

    solve(collapsed_results)

    # 输出所有解
    print(f"共找到{len(solutions)}个有效解：")
    for idx, sol in enumerate(solutions):
        print(f"解{idx+1}:")
        for row in sol:
            print(' '.join(row))

使用示例 #

输入示例损坏数据：

1 2 2
2 1 1

运行输出结果：

共找到1个有效解：
解1:
1 2 _
_ 1 2
2 _ 1

如果存在多个符合规则的还原结果，会依次输出所有解。

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