每日算法 — 使用java实现循环赛日程表：分治策略与镜像填充算法

循环赛日程表是算法分治策略的经典应用之一。问题描述为：有 $n$ 名选手（$n = 2^k$）参加循环赛，要求每名选手与其他 $n-1$ 名选手各比赛一次，每天每名选手只比赛一次，问最少需要多少天以及如何安排赛程？

问题分析

循环赛日程表问题的核心在于：如何在 $n-1$ 天内，为 $n$ 名选手安排 $n-1$ 轮比赛，使得每名选手每天恰好比赛一次且不重复对阵。当 $n = 2^k$ 时，最少需要 $n-1$ 天即可完成全部比赛。

该问题的最优解可以通过分治策略构造：将 $n$ 名选手分成两半，分别解决子问题，然后通过镜像复制完成合并。

算法核心思想

分治构造法的核心步骤如下：

基本情况：当 $n = 2$ 时，直接安排两名选手对阵即可
分解：将 $n$ 名选手分为两组，每组 $n/2$ 人
递归解决：分别为两组选手构造各自的循环赛日程表
合并：将右下角的子表复制到左上角，左下角的子表复制到右上角

通过镜像复制，可以确保新加入的选手与原有所有选手各比赛一次。

Java完整实现

import java.util.Arrays;

/**
 * 循环赛日程表 - 分治策略实现
 * 问题：n = 2^k 名选手进行循环赛，求最优日程安排
 */
public class RoundRobinSchedule {

    /**
     * 生成循环赛日程表
     * @param k 幂次，选手数量 n = 2^k
     * @return 日程表，schedule[i][j] 表示第 i 名选手在第 j 天的对手
     */
    public static int[][] generateSchedule(int k) {
        int n = 1 << k; // n = 2^k
        int[][] schedule = new int[n + 1][n]; // 1-based indexing for players

        // 基本情况：2名选手
        schedule[1][1] = 2;
        schedule[2][1] = 1;

        // 迭代扩展：从2人扩展到n人
        int currentSize = 2;
        while (currentSize < n) {
            // 将当前日程表复制到右下、左下、右上
            for (int i = 1; i <= currentSize; i++) {
                for (int j = 1; j <= currentSize - 1; j++) {
                    // 右上角：原日程表 + currentSize
                    schedule[i][j + currentSize - 1] = schedule[i][j] + currentSize;
                    // 左下角：镜像复制
                    schedule[i + currentSize][j] = schedule[i][j] + currentSize;
                }
                // 右下角
                schedule[i + currentSize][currentSize - 1 + currentSize] = schedule[i][currentSize - 1] + currentSize;
            }
            // 新加入的对角线位置（第currentSize天）
            for (int i = 1; i <= currentSize; i++) {
                schedule[i][currentSize] = i + currentSize;
                schedule[i + currentSize][currentSize] = i;
            }
            currentSize *= 2;
        }

        return schedule;
    }

    /**
     * 更规范的分治递归实现
     */
    public static void generateRecursive(int[][] table, int startRow, int startCol, int size) {
        if (size == 2) {
            // 2x2 基础块
            table[startRow][startCol] = startRow + 1;
            table[startRow + 1][startCol] = startRow;
            return;
        }

        int half = size / 2;

        // 递归填充左上象限
        generateRecursive(table, startRow, startCol, half);

        // 复制到右下象限（左上 + half）
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half - 1; j++) {
                table[startRow + half + i][startCol + half - 1 + j] = 
                    table[startRow + i][startCol + j] + half;
            }
        }

        // 复制到左下象限（右上镜像）
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half - 1; j++) {
                table[startRow + half + i][startCol + j] = 
                    table[startRow + i][startCol + half - 1 + j];
            }
        }

        // 复制到右上象限（左下镜像）
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half - 1; j++) {
                table[startRow + i][startCol + half - 1 + j] = 
                    table[startRow + half + i][startCol + j];
            }
        }

        // 填充中间列（新加入的对角线）
        for (int i = 0; i < half; i++) {
            table[startRow + i][startCol + half - 1] = startRow + half + i;
            table[startRow + half + i][startCol + half - 1] = startRow + i;
        }
    }

    /**
     * 打印日程表（更清晰的格式）
     */
    public static void printSchedule(int[][] schedule, int n) {
        System.out.println("循环赛日程表（选手数 n=" + n + "，比赛天数=" + (n - 1) + "）");
        System.out.println("行=选手编号，列=比赛日，值=当天对手编号");
        System.out.println("------------------------------------------------");

        for (int i = 1; i <= n; i++) {
            System.out.printf("选手 %2d: ", i);
            for (int j = 1; j <= n - 1; j++) {
                System.out.printf("%3d", schedule[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 验证日程表的正确性
     */
    public static boolean validate(int[][] schedule, int n) {
        // 每名选手每天只有一个对手
        for (int day = 1; day <= n - 1; day++) {
            boolean[] seen = new boolean[n + 1];
            for (int player = 1; player <= n; player++) {
                int opponent = schedule[player][day];
                if (opponent < 1 || opponent > n || opponent == player) {
                    return false;
                }
                if (seen[opponent]) {
                    return false; // 对手重复
                }
                seen[opponent] = true;
                // 对称性检查
                if (schedule[opponent][day] != player) {
                    return false;
                }
            }
        }

        // 每名选手与其他所有选手恰好比赛一次
        for (int player = 1; player <= n; player++) {
            boolean[] played = new boolean[n + 1];
            for (int day = 1; day <= n - 1; day++) {
                played[schedule[player][day]] = true;
            }
            for (int opp = 1; opp <= n; opp++) {
                if (opp != player && !played[opp]) {
                    return false;
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {
        int k = 3; // 8名选手
        int n = 1 << k;

        // 迭代法
        int[][] schedule = generateSchedule(k);
        printSchedule(schedule, n);
        System.out.println("\n验证结果: " + (validate(schedule, n) ? "通过" : "失败"));

        System.out.println("\n" + "=".repeat(50) + "\n");

        // 递归法
        int[][] recursiveTable = new int[n + 1][n];
        generateRecursive(recursiveTable, 1, 1, n);
        printSchedule(recursiveTable, n);
        System.out.println("\n验证结果: " + (validate(recursiveTable, n) ? "通过" : "失败"));
    }
}

时间复杂度分析

分治构造循环赛日程表的时间复杂度为 $T(n) = 4T(n/2) + O(n^2)$，根据主定理可得 $T(n) = O(n^2 \log n)$。由于需要填充 $n \times (n-1)$ 的表格，空间复杂度为 $O(n^2)$。

算法拓展

当选手数量不是2的幂次时，可以引入虚拟选手（bye）进行填充。对于奇数 $n$，最少需要 $n$ 天完成比赛，每天有1名选手轮空。分治框架依然适用，只需在合并阶段处理边界情况。

Tagged with: 分治策略循环赛日程表递归算法镜像填充