歡迎來(lái)到「我是真的狗雜談世界」干跛，關(guān)注不迷路
背景/前言
最近遇到了兩個(gè)可以轉(zhuǎn)化為本文題目問(wèn)題的需求點(diǎn)（具體需求在下面應(yīng)用節(jié)選會(huì)講到），決定整理和記錄下來(lái)祟绊。
技術(shù)問(wèn)題描述
- 問(wèn)題：給定一個(gè)連續(xù)且有限的值范圍（從min到max楼入，步長(zhǎng)為step），從中隨機(jī)取出不重復(fù)的n個(gè)值牧抽。
- 舉例：從108～10086的整數(shù)范圍內(nèi)嘉熊，取出10個(gè)不重復(fù)的隨機(jī)數(shù)。
技術(shù)問(wèn)題方案
解決問(wèn)題總會(huì)有一些通用的思想扬舒，比如：窮舉阐肤、分治、迭代讲坎、倍增孕惜、回溯、貪心晨炕、動(dòng)規(guī)
那運(yùn)用這些思想可以想到如下解法（當(dāng)然還會(huì)有別的解法）
粗暴隨機(jī)法
- 維護(hù)一個(gè)結(jié)果集
- 在范圍內(nèi)生成一個(gè)隨機(jī)數(shù)衫画，并判斷隨機(jī)數(shù)是否在結(jié)果集內(nèi)
- 隨機(jī)數(shù)不在結(jié)果集內(nèi)則加入結(jié)果集，并回到2步驟直至結(jié)果集內(nèi)數(shù)量滿足
- 隨機(jī)數(shù)在結(jié)果集內(nèi)則直接回到2步驟直至結(jié)果集內(nèi)數(shù)量滿足
function unique_rand($min, $max, $num) {
$count = 0;
$return = [];
while ($count < $num) {
$return[] = mt_rand($min, $max);
// 借助翻轉(zhuǎn)法識(shí)別并剔除重復(fù)值
$return = array_flip(array_flip($return));
$count = count($return);
}
shuffle($return);
return $return;
}
剔除隨機(jī)法
- 窮舉全量范圍并構(gòu)建數(shù)組（k1=min,k2=min+step,kx=min+(x-1)*step,...kn=max）
- 每次在k范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)a府瞄，并將ka的值放入結(jié)果集碧磅，同時(shí)用kn的值填充ka碘箍，n自減
- 重復(fù)2步驟直至結(jié)果集內(nèi)數(shù)量滿足
function unique_rand($min, $max, $num) {
$numbers = range($min, $max);
// 實(shí)現(xiàn)上偷個(gè)懶遵馆，直接采用內(nèi)置打亂函數(shù)，再取前多少位的方式
shuffle($numbers);
$result = array_slice($numbers, 0, $num);
return $result;
}
均勻分布法
- 將全量范圍分為均勻的n段子范圍
- 從每一段中獲取一個(gè)隨機(jī)數(shù)放入結(jié)果集
再升級(jí)一下就是雙倍隨機(jī)法（但雙倍隨機(jī)法需要處理額度不足問(wèn)題）
// 代碼就偷個(gè)懶不寫了
語(yǔ)言內(nèi)置函數(shù)/標(biāo)準(zhǔn)庫(kù)
有的語(yǔ)言可能內(nèi)置了相關(guān)方法丰榴，比如
/**
* 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 {}
技術(shù)問(wèn)題場(chǎng)景
場(chǎng)景羅列
不同的方案肯定各有優(yōu)劣货邓，需要結(jié)合具體場(chǎng)景來(lái)分析。
我們先考慮一下影響實(shí)現(xiàn)的維度有：
- 范圍基數(shù): c = ((max-min)/step)+1四濒；這個(gè)值有大/小的維度取值
- 目標(biāo)結(jié)果比例: r = n/c换况；這個(gè)值有少/中/多的維度取值
因?yàn)槲覀兛梢粤_列場(chǎng)景如下：
- c小r少： 比如從100個(gè)里面產(chǎn)生3個(gè)
- c小r中： 比如從100個(gè)里面產(chǎn)生48個(gè)
- c小r多： 比如從100個(gè)里面產(chǎn)生97個(gè)
- c大r少： 比如從1000000個(gè)里面產(chǎn)生10個(gè)
- c大r中： 比如從1000000個(gè)里面產(chǎn)生489876個(gè)
- c大r多： 比如從1000000個(gè)里面產(chǎn)生999997個(gè)
但考慮到3和6兩種r多的情況可以時(shí)1和4情況的取反职辨，因此合并：
- c小r少： 比如從100個(gè)里面產(chǎn)生3個(gè)
- c小r中： 比如從100個(gè)里面產(chǎn)生48個(gè)
- c大r少： 比如從1000000個(gè)里面產(chǎn)生10個(gè)
- c大r中： 比如從1000000個(gè)里面產(chǎn)生489876個(gè)
場(chǎng)景與解法匹配
可以多種解法混用
| c小r少 | c小r中 | c大r少 | c大r中 | |
|---|---|---|---|---|
| 粗暴隨機(jī)法 | 高 [1] | 低 [2] | 高 [1] | 低 [2] |
| 剔除隨機(jī)法 | 高? [3] | 高 [3] | 低 [4] | 低 [4] |
| 均勻分布法 | 低? [5] | 高 [6] | 低 [5] | 高 [6] |
業(yè)務(wù)應(yīng)用
連抽N份獎(jiǎng)品
- 需求描述：用戶達(dá)成特定任務(wù)后有資格參與最終的抽獎(jiǎng)環(huán)節(jié)，在抽獎(jiǎng)環(huán)節(jié)通過(guò)管理后臺(tái)進(jìn)行中獎(jiǎng)人員抽取戈二，同等級(jí)獎(jiǎng)品需同時(shí)抽出
- 轉(zhuǎn)換關(guān)聯(lián)：將有資格的用戶放在一張表中舒裤，抽取時(shí)獲取最新記錄自增ID N，就轉(zhuǎn)換成了從1～N中生成X個(gè)不重復(fù)隨機(jī)數(shù)的問(wèn)題
紅包瓜分（搶紅包）
- 需求描述：一個(gè)房間有N個(gè)座位觉吭，每個(gè)座位可以讓一個(gè)人入座參與一場(chǎng)單人小游戲（不需要同時(shí)開局同時(shí)結(jié)束）腾供，且一個(gè)房間對(duì)應(yīng)一定金額的紅包A，每個(gè)人完成單人小游戲后可以瓜分其中一定的金額
- 轉(zhuǎn)換關(guān)聯(lián)：?jiǎn)稳送瓿捎螒虻臅r(shí)間點(diǎn)是不同的鲜滩，但可以將紅包額度瓜分的時(shí)機(jī)前置到房間初始化之時(shí)伴鳖，再結(jié)合線段分割法，就轉(zhuǎn)換成了先從0～A中生成N-1個(gè)不重復(fù)隨機(jī)數(shù)徙硅，再以這N-1個(gè)隨機(jī)數(shù)排序座位切割點(diǎn)構(gòu)成N段隨機(jī)長(zhǎng)度問(wèn)題
