從陣列隨機抽取不重複元素：兩種演算法對比分析

從無重複陣列中隨機抽取指定數量的不重複元素，核心挑戰在於避免重複抽取（特別是接近尾聲時），需盡可能降低碰撞機率。本文分析兩種不同策略的實作與效能差異。

演算法一：隨機標記法（CSDN 參考方案）

$num = 0;
$array = range(1, 9);
$arr = [];
$g = 5;  // 需抽取數量
$tag = true;

while ($tag) {
    $count = count($array);
    $t = rand(0, 1);  // 50% 機率選取
    if ($t == 1) {
        $arr[] = $array[$num];
        unset($array[$num]);  // 移除已選元素
    }
    $num++;
    if (count($arr) == $g) $tag = false;
    if ($num == $count) $num = 0;  // 循環遍歷
}
var_dump($arr);

缺點：隨機性依賴硬幣擲擲，效率不穩定；unset 導致陣列索引不連續，需額外處理。

演算法二：交換法（推薦方案）

function swap(&$a, &$b) {
    $temp = $b; $b = $a; $a = $temp;
}

$src = range(1, 40);
$arr_len = count($src);
$count = 20;  // 抽取數量
$index = 0;
$result = [];

while ($index < $count) {
    $random = rand(0, $arr_len - $index - 1);
    $result[] = $src[$random];
    // 關鍵：將已選元素與未選區域末尾交換
    swap($src[$random], $src[$arr_len - $index - 1]);
    $index++;
}

print_r(json_encode($result));
print_r(json_encode($src));

核心優勢分析

原理圖解

交換法維護一個「未選區域」[0, arr_len - index - 1]，每次從中隨機選取並與區域末尾交換，確保：

1. 已選元素移至陣列尾部，不再參與後續隨機
2. 未選區域緊湊連續，隨機索引直接對應有效元素
3. 無需額外標記陣列或雜湊表

推廣應用

此演算法即為 Fisher-Yates Shuffle 的部分執行版本，廣泛應用於：

• 抽獎系統、隨機抽樣
• 遊戲開發：洗牌、隨機生成關卡
• 機器學習：資料集隨機切分