歡迎來到「我是真的狗雜談世界」，關注不迷路

背景/前言

最近遇到了兩個可以轉化為本文題目問題的需求點（具體需求在下面應用節選會講到），決定整理和記錄下來。

技術問題描述

• 問題：給定一個連續且有限的值範圍（從min到max，步長為step），從中隨機取出不重複的n個值。
• 舉例：從108～10086的整數範圍內，取出10個不重複的隨機數。

技術問題方案

解決問題總會有一些通用的思想，比如：窮舉、分治、迭代、倍增、回溯、貪心、動規

那運用這些思想可以想到如下解法（當然還會有別的解法）

粗暴隨機法

1. 維護一個結果集
2. 在範圍內生成一個隨機數，並判斷隨機數是否在結果集內
3. 隨機數不在結果集內則加入結果集，並回到2步驟直至結果集內數量滿足
4. 隨機數在結果集內則直接回到2步驟直至結果集內數量滿足

function unique_rand($min, $max, $num) {
    $count = 0;
    $return = [];
    while ($count < $num) {
        $return[] = mt_rand($min, $max);
        // 藉助翻轉法識別並剔除重複值
        $return = array_flip(array_flip($return));
        $count = count($return);
    }
    shuffle($return);
    return $return;
}

剔除隨機法

1. 窮舉全量範圍並構建數組（k1=min,k2=min+step,kx=min+(x-1)*step,...kn=max）
2. 每次在k範圍內產生一個隨機數a，並將ka的值放入結果集，同時用kn的值填充ka，n自減
3. 重複2步驟直至結果集內數量滿足

function unique_rand($min, $max, $num) {
    $numbers = range($min, $max);
    // 實現上偷個懶，直接採用內置打亂函數，再取前多少位的方式
    shuffle($numbers);
    $result = array_slice($numbers, 0, $num);
    return $result;
}

均勻分佈法

1. 將全量範圍分為均勻的n段子範圍
2. 從每一段中獲取一個隨機數放入結果集

再升級一下就是雙倍隨機法（但雙倍隨機法需要處理額度不足問題）

// 代碼就偷個懶不寫了

語言內置函數/標準庫

有的語言可能內置了相關方法，比如

/**
 * Pick one or more random keys out of an array
 * @link https://php.net/manual/en/function.array-rand.php
 * @param array $array <p>
 * The input array.
 * </p>
 * @param int $num [optional] <p>
 * Specifies how many entries you want to pick.
 * </p>
 * @return int|string|array If you are picking only one entry, array_rand
 * returns the key for a random entry. Otherwise, it returns an array
 * of keys for the random entries. This is done so that you can pick
 * random keys as well as values out of the array.
 */
function array_rand(array $array, int $num = 1): array|string|int {}

技術問題場景

場景羅列

不同的方案肯定各有優劣，需要結合具體場景來分析。
我們先考慮一下影響實現的維度有：

• 範圍基數: c = ((max-min)/step)+1；這個值有大/小的維度取值
• 目標結果比例: r = n/c；這個值有少/中/多的維度取值

因為我們可以羅列場景如下：

1. c小r少： 比如從100個裏面產生3個
2. c小r中： 比如從100個裏面產生48個
3. c小r多： 比如從100個裏面產生97個
4. c大r少： 比如從1000000個裏面產生10個
5. c大r中： 比如從1000000個裏面產生489876個
6. c大r多： 比如從1000000個裏面產生999997個

但考慮到3和6兩種r多的情況可以時1和4情況的取反，因此合併：

1. c小r少： 比如從100個裏面產生3個
2. c小r中： 比如從100個裏面產生48個
3. c大r少： 比如從1000000個裏面產生10個
4. c大r中： 比如從1000000個裏面產生489876個

場景與解法匹配

可以多種解法混用

業務應用

連抽N份獎品

• 需求描述：用户達成特定任務後有資格參與最終的抽獎環節，在抽獎環節通過管理後台進行中獎人員抽取，同等級獎品需同時抽出
• 轉換關聯：將有資格的用户放在一張表中，抽取時獲取最新記錄自增ID N，就轉換成了從1～N中生成X個不重複隨機數的問題

紅包瓜分（搶紅包）

• 需求描述：一個房間有N個座位，每個座位可以讓一個人入座參與一場單人小遊戲（不需要同時開局同時結束），且一個房間對應一定金額的紅包A，每個人完成單人小遊戲後可以瓜分其中一定的金額
• 轉換關聯：單人完成遊戲的時間點是不同的，但可以將紅包額度瓜分的時機前置到房間初始化之時，再結合線段分割法，就轉換成了先從0～A中生成N-1個不重複隨機數，再以這N-1個隨機數排序座位切割點構成N段隨機長度問題