您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 實現洗牌發牌算法：從 Fisher-Yates 到實戰鬥地主/橋牌模擬

編輯：Java 相關知識

核心算法：Fisher-Yates Shuffle (Knuth Shuffle)

標準洗牌算法要求：每種排列出現概率均等 (1/n!)。Fisher-Yates 算法通過從後向前遍歷，每次從未洗部分隨機選一張與當前位置交換，時間複雜度 O(n)，空間 O(1)，且無偏差。

public static void shuffle(List list, Random random) {
    for (int i = list.size() - 1; i > 0; i--) {
        int j = random.nextInt(i + 1); // [0, i]
        Collections.swap(list, i, j);
    }
}

完整發牌模擬框架

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class CardGameSimulator {
    
    // === 域模型 ===
    enum Suit { SPADE("♠"), HEART("♥"), CLUB("♣"), DIAMOND("♦");
        final String symbol;
        Suit(String s) { this.symbol = s; }
        @Override public String toString() { return symbol; }
    }
    
    enum Rank { 
        ACE("A"), TWO("2"), THREE("3"), FOUR("4"), FIVE("5"), SIX("6"), 
        SEVEN("7"), EIGHT("8"), NINE("9"), TEN("10"), JACK("J"), QUEEN("Q"), KING("K");
        final String symbol;
        Rank(String s) { this.symbol = s; }
        @Override public String toString() { return symbol; }
    }
    
    record Card(Suit suit, Rank rank) {
        @Override public String toString() { return suit + rank; }
    }
    
    record Player(String name, List hand) {
        public void sortHand() {
            hand.sort(Comparator
                .comparing((Card c) -> c.suit.ordinal())
                .thenComparing(c -> c.rank.ordinal()));
        }
        @Override public String toString() {
            return name + ": " + hand.stream().map(Object::toString).collect(Collectors.joining(" "));
        }
    }
    
    // === 核心邏輯 ===
    private final List deck = new ArrayList<>(52);
    private final List players = new ArrayList<>();
    private final Random random = new Random();
    
    public CardGameSimulator() {
        // 初始化標準 52 張牌
        for (Suit s : Suit.values()) {
            for (Rank r : Rank.values()) {
                deck.add(new Card(s, r));
            }
        }
    }
    
    public void addPlayer(String name) {
        players.add(new Player(name, new ArrayList<>()));
    }
    
    /** 洗牌 */
    public void shuffle() {
        for (int i = deck.size() - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            Card tmp = deck.get(i);
            deck.set(i, deck.get(j));
            deck.set(j, tmp);
        }
    }
    
    /** 發牌：平均分配，餘牌留在牌堆 */
    public void deal(int cardsPerPlayer) {
        if (players.isEmpty()) throw new IllegalStateException("無玩家");
        if (cardsPerPlayer * players.size() > deck.size()) 
            throw new IllegalArgumentException("牌不夠發");
        
        for (int round = 0; round < cardsPerPlayer; round++) {
            for (Player p : players) {
                p.hand().add(deck.remove(deck.size() - 1)); // 從牌堆頂發牌
            }
        }
    }
    
    /** 發牌：指定每人牌數 (如鬥地主 17/17/17+3) */
    public void dealCustom(int... cardsPerPlayer) {
        if (cardsPerPlayer.length != players.size()) 
            throw new IllegalArgumentException("玩家數不匹配");
        int total = Arrays.stream(cardsPerPlayer).sum();
        if (total > deck.size()) throw new IllegalArgumentException("牌不夠");
        
        for (int i = 0; i < players.size(); i++) {
            Player p = players.get(i);
            for (int c = 0; c < cardsPerPlayer[i]; c++) {
                p.hand().add(deck.remove(deck.size() - 1));
            }
        }
    }
    
    public void printHands() {
        players.forEach(p -> {
            p.sortHand();
            System.out.println(p);
        });
        System.out.println("剩餘牌堆: " + deck.size() + " 張");
    }
    
    // === 場景演示 ===
    public static void main(String[] args) {
        // 場景 1：橋牌 - 4 人各 13 張
        System.out.println("=== 橋牌發牌 ===");
        CardGameSimulator bridge = new CardGameSimulator();
        bridge.addPlayer("北");
        bridge.addPlayer("東");
        bridge.addPlayer("南");
        bridge.addPlayer("西");
        bridge.shuffle();
        bridge.deal(13);
        bridge.printHands();
        
        // 場景 2：鬥地主 - 3 人 17/17/17 + 3 底牌
        System.out.println("\n=== 鬥地主發牌 ===");
        CardGameSimulator doudizhu = new CardGameSimulator();
        doudizhu.addPlayer("農民甲");
        doudizhu.addPlayer("地主");
        doudizhu.addPlayer("農民乙");
        doudizhu.shuffle();
        doudizhu.dealCustom(17, 17, 17);
        doudizhu.printHands();
        System.out.println("底牌: " + doudizhu.deck); // 剩餘 3 張
        
        // 場景 3：德州撲克 - 2 人各 2 張 + 5 張公共牌
        System.out.println("\n=== 德州撲克發牌 ===");
        CardGameSimulator holdem = new CardGameSimulator();
        holdem.addPlayer("玩家A");
        holdem.addPlayer("玩家B");
        holdem.shuffle();
        holdem.deal(2);
        List community = new ArrayList<>();
        for (int i = 0; i < 5; i++) community.add(holdem.deck.remove(holdem.deck.size() - 1));
        holdem.printHands();
        System.out.println("公共牌: " + community);
    }
}

進階：加入大小王 (54 張牌)

enum Rank {
    // ... 原有 13 張 ...
    JOKER_SMALL("🃏"), JOKER_BIG("🃏"); // 或用 "小王", "大王"
    // 在初始化牌組時添加
    // deck.add(new Card(null, Rank.JOKER_SMALL));
    // deck.add(new Card(null, Rank.JOKER_BIG));
    // Comparator 需處理 null suit
}

線程安全與可重複性

線程安全：`Random` 非線程安全，多線程環境使用 `ThreadLocalRandom.current()` 或每線程獨立 `Random` 實例
可重複性 (測試/回放)：使用固定種子 `new Random(seed)`，相同種子產生相同洗牌序列
加密安全：賭場級應用需 `SecureRandom`，防止預測

性能基準 (JMH 參考)

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ShuffleBenchmark {
    private List deck = IntStream.range(0, 52).boxed().collect(Collectors.toList());
    
    @Benchmark
    public void collectionsShuffle() { Collections.shuffle(deck); }
    
    @Benchmark
    public void fisherYates() { 
        for (int i = deck.size()-1; i>0; i--) 
            Collections.swap(deck, i, ThreadLocalRandom.current().nextInt(i+1)); 
    }
}
// 典型結果: Collections.shuffle ~300ns/op, 手寫 Fisher-Yates ~250ns/op (避免了 List 介面調用開銷)

常見錯誤與修正

錯誤寫法	問題	修正
`for(i=0; i	偏差：首元素被交換機會過高	從後向前 `for(i=n-1; i>0; i--) swap(i, random.nextInt(i+1))`
`random.nextInt(n-1)`	漏掉最後一個元素	`random.nextInt(i+1)` 範圍 [0, i]
使用 `Math.random()`	精度低、性能差、非線程安全	`Random` / `ThreadLocalRandom` / `SecureRandom`
洗牌後用 `subList` 發牌不清理原列表	內存洩漏、索引錯亂	用 `remove` 移出或維護指針索引

擴展：自定義規則引擎

@FunctionalInterface
interface DealRule {
    void deal(CardGameSimulator sim);
}

// 註冊規則
Map rules = Map.of(
    "bridge", sim -> sim.deal(13),
    "doudizhu", sim -> sim.dealCustom(17,17,17),
    "poker", sim -> { sim.deal(2); /* 公共牌邏輯 */ }
);

// 動態選擇
rules.get(gameType).deal(simulator);

洗牌發牌是經典算法面試題，更是遊戲開發、抽獎系統、負載均衡 (一致性哈希虛擬節點洗牌) 的基石。掌握 Fisher-Yates 正確性證明、邊界條件處理、隨機源選擇，能讓你在需要「公平隨機」的任何場景寫出可靠代碼。