「隨機抽 N 個不重複的數字」是很常遇到的需求:抽獎名單、隨機出題、打亂順序等等。直覺做法是邊抽邊檢查有沒有重複,但這個做法的效率其實很差。
// 用來存放已產生的隨機數
var array = [];
// 迴圈直到湊滿 10 個
while (array.length < 10){
generateRandom(10);
}
// 逐一輸出
for (var i = 0; i < array.length; i++){
alert(array[i]);
}
// 產生隨機數並去重
function generateRandom(count){
var rand = parseInt(Math.random() * count);
for (var i = 0; i < array.length; i++){
if (array[i] == rand){
return false; // 已存在,放棄這次
}
}
array.push(rand);
}
原範例用 for(var i = 0; ; i++) 這種刻意留空的寫法當無限迴圈,改成 while (array.length < 10) 語意更清楚,也不會有未使用變數。
每次產生新數字,都要跟已產生的全部比對一次,整體是 O(n²)。更糟的是當 count 接近 array.length 時,碰撞機率急遽升高,迴圈可能空轉很多次。舉例來說,要從 1 到 10 抽 9 個不重複數字,最後一個的平均嘗試次數會是 10 次;若不小心寫成抽 10 個,parseInt(Math.random()*10) 有可能一直取不到剩下那一個,迴圈就永遠停不下來。
另外 parseInt(Math.random() * count) 在多數瀏覽器可正常運作,但 parseInt 少了第二個基数參數是不良習慣,改用 Math.floor() 更明確。
function getRandomUnique(count, max){
var set = new Set();
while (set.size < count){
set.add(Math.floor(Math.random() * max));
}
return Array.from(set);
}
用 Set 取代陣列,加入與查詢都是 O(1),省掉了內層的線性搜尋。前提是 count <= max,否則一樣會無限迴圈,記得加上防呆:
if (count > max) throw new RangeError('抽出的數量不能超過範圍大小');
如果 count 相對於 max 不算太小,最有效率的做法是「先洗牌再取前 N 個」,時間複雜度固定 O(max),完全沒有碰撞問題:
function shuffle(arr){
for (var i = arr.length - 1; i > 0; i--){
var j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}
function getRandomUnique(count, max){
var pool = [];
for (var i = 1; i <= max; i++) pool.push(i);
return shuffle(pool).slice(0, count);
}
getRandomUnique(5, 10); // 例如 [7, 2, 9, 1, 5]
Fisher-Yates 是公認最公平的洗牌演算法,每個排列組合出現的機率完全相同。用它來抽不重複隨機數,速度快、結果均勻,也不會有停不下來的風險。
抽少量、範圍大:用 Set 湊數即可。抽很多、範圍不大:直接洗牌取前段。無論哪種,都要記得檢查 count 是否超過範圍上限,這是最常見的無限迴圈元凶。