歡迎來(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ī)法

1. 維護(hù)一個(gè)結(jié)果集
2. 在范圍內(nèi)生成一個(gè)隨機(jī)數(shù)，并判斷隨機(jī)數(shù)是否在結(jié)果集內(nèi)
3. 隨機(jī)數(shù)不在結(jié)果集內(nèi)則加入結(jié)果集，并回到2步驟直至結(jié)果集內(nèi)數(shù)量滿足
4. 隨機(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ī)法

1. 窮舉全量范圍并構(gòu)建數(shù)組（k1=min,k2=min+step,kx=min+(x-1)*step,...kn=max）
2. 每次在k范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)a，并將ka的值放入結(jié)果集，同時(shí)用kn的值填充ka，n自減
3. 重復(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;
}

均勻分布法

1. 將全量范圍分為均勻的n段子范圍
2. 從每一段中獲取一個(gè)隨機(jī)數(shù)放入結(jié)果集

再升級(jí)一下就是雙倍隨機(jī)法（但雙倍隨機(jī)法需要處理額度不足問(wèn)題）

// 代碼就偷個(gè)懶不寫(xiě)了

語(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)景如下：

1. c小r少： 比如從100個(gè)里面產(chǎn)生3個(gè)
2. c小r中： 比如從100個(gè)里面產(chǎn)生48個(gè)
3. c小r多： 比如從100個(gè)里面產(chǎn)生97個(gè)
4. c大r少： 比如從1000000個(gè)里面產(chǎn)生10個(gè)
5. c大r中： 比如從1000000個(gè)里面產(chǎn)生489876個(gè)
6. c大r多： 比如從1000000個(gè)里面產(chǎn)生999997個(gè)

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

1. c小r少： 比如從100個(gè)里面產(chǎn)生3個(gè)
2. c小r中： 比如從100個(gè)里面產(chǎn)生48個(gè)
3. c大r少： 比如從1000000個(gè)里面產(chǎn)生10個(gè)
4. c大r中： 比如從1000000個(gè)里面產(chǎn)生489876個(gè)

場(chǎng)景與解法匹配

可以多種解法混用

業(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í)開(kāi)局同時(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)題

1. r少，不容易生成重復(fù)值導(dǎo)致時(shí)間復(fù)雜度升高 ? ?

2. r中，容易生成重復(fù)值導(dǎo)致時(shí)間復(fù)雜度升高 ? ?

3. c小，內(nèi)存容納得下，通過(guò)時(shí)間換空間 ? ?

4. c大，內(nèi)存分配消耗增大，且可能內(nèi)存不足 ? ?

5. r少，結(jié)果分布會(huì)比較均勻，如果要求隨機(jī)性高則不適用 ? ?

6. r中，結(jié)果分布本身跟隨概率分布就會(huì)比較均勻，因此此方法匹配度上升 ? ?