Java 實現打地鼠遊戲：如何高效生成不重複的隨機位置？

問題本質

在 4×4 網格（16 個位置）中，每輪隨機選取一個未出現過的位置顯示地鼠，直到所有位置都出現過一次。初學者常用「隨機 + 重試」導致末期極其低效（期望嘗試次數 ∑ 16/(16-k) ≈ 54 次，實際常超百次）。

最優解：洗牌算法—— 一次打亂，順序取用

將 16 個位置放入列表，Fisher-Yates 洗牌 打亂，然後按順序彈出，保證：

• 每個位置恰好出現一次
• 全程無重試、無衝突
• 時間複雜度 O(n)，空間 O(n)

完整實現代碼

import java.util.*;

public class WhacAMole {
    private final List positions = new ArrayList<>(16);
    private int index = 0;

    public WhacAMole(int rows, int cols) {
        // 1. 初始化所有位置
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                positions.add(new int[]{r, c});
            }
        }
        // 2. 洗牌
        Collections.shuffle(positions);
    }

    /** 獲取下一個不重複位置，無則返回 null */
    public int[] nextPosition() {
        if (index >= positions.size()) return null;
        return positions.get(index++);
    }

    /** 重置遊戲 */
    public void reset() {
        index = 0;
        Collections.shuffle(positions);
    }

    // 測試
    public static void main(String[] args) {
        WhacAMole game = new WhacAMole(4, 4);
        int[] pos;
        while ((pos = game.nextPosition()) != null) {
            System.out.printf("地鼠出現：(%d, %d)%n", pos[0], pos[1]);
        }
        System.out.println("所有位置已出現，遊戲結束。");
    }
}

進階：支持「多輪遊戲」與「動態網格」

public class FlexibleMoleGame {
    private final int rows, cols;
    private List pool;
    private int ptr;

    public FlexibleMoleGame(int rows, int cols) {
        this.rows = rows; this.cols = cols;
        reset();
    }

    public void reset() {
        pool = new ArrayList<>(rows * cols);
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                pool.add(new int[]{r, c});
        Collections.shuffle(pool);
        ptr = 0;
    }

    public int[] next() {
        if (ptr >= pool.size()) return null; // 本輪結束
        return pool.get(ptr++);
    }

    // 若需「隨機但允許重複」，另寫一個隨機生成器即可
}

為什麼不用「隨機 + Set 去重」？

核心 API 解析

• Collections.shuffle(list)：默認使用 `Random`，內部實現為 Fisher-Yates，線程不安全，單線程遊戲循環完全足夠。
• 若需可復現（如回放、測試），可傳入固定種子：`new Random(12345L)` → `Collections.shuffle(list, random)`。

總結

「打地鼠」類無放回抽樣場景，**洗牌算法是教科書級最優解**。拒絕「隨機重試」，拥抱 `Collections.shuffle`，代碼更短、跑得更快、邏輯更清晰。