从 n 个数里面随机取 m 个数

电话面试被问了一个很有趣的问题：给一个函数 getRandom(x) 能随机返回[0,x) 中的一个数，求实现一个 RandomNumberGenerator(n) 数据结构，里面有一个 generate() 接口，要求每次调用随机返回[0,n) 中的一个数，同时不能返回已经返回过的数。

这个题换一种说法其实就是从 n 个数里面随机取 m 个数。工作中经常遇到类似的问题，一般调用已有库函数就可以实现，所以从来没有想过这个方法的具体实现。

最简单的暴力解法，用一个 Set 来保存已经出现的数，generate() 函数不停地调用 getRandom(n)，直到生成的数字不在 set 里面，返回这个数，同时把这个数加进 Set 。这个解法最坏情况可能导致无限死循环，假设 Set 里面数字个数为 m ，那么每次成功的概率为 (n - m) / n ，如果 n 和 m 十分接近，则这个概率会很小。这个解法不被接受。

要求一个是肯定有解的算法。自己想了几个 [算法] 从 n 个数里面随机取 m 个数，不知道有没有更好的解法。

meilicat

31 天前

参考 oiwiki
https://oi-wiki.org/misc/random/#%E9%9A%8F%E6%9C%BA%E6%95%B0%E4%B8%8E%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%95%B0

pkoukk

31 天前

getRandom 本身并不能保证不返回重复的数吧？
那 RandomNumberGenerator 里肯定就要包含一个 Set 啊
初始化的时候持续调用 getRandom 获取 n 个不重复的随机数
然后 generate() 顺序返回就可以了吧

liuhuan475

31 天前

@abc0def 自己打乱一下也不难

baislsl

31 天前

array shuffle 的算法
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

按照'opposite direction'实现, 每次循环返回 a[i]

poorLi

31 天前

洗牌算法了解下

forty

31 天前

思路 1：通用的线性同余伪随机数生成算法，在 1 个周期内不会重复，编程语言里自带的随机数发生器一般都是它。你只要记住每次的种子就行了，保证你在用完每个数之前都不会重复。这个算法甚至都不需要用到题目提供的函数 getRandom(x) 。

思路 2：先用洗牌算法打乱，然后挨个取，保证不重复。但不适合数量太大的情况。比如从 2^32 个数里面随机取 2^16 个数，就没那么大的内存了，此时要用思路 1 更合适。

Lhcfl

31 天前

很好写啊，用一个伪的数组。已知 array shuffle 是每次将 a[i] 与 a[i ~ n] 中的某个元素交换。你把这个过程 lazy 一下，每次 generate 就输出 (mapped[i] || i) swap (getRandom(n-i) + i)，这样每次操作都是 O(1)的，空间也是复杂度也很优秀。

wuyadaxian

31 天前

又重新思考了下，楼主说的 [最简单的解法] 才是最好的解法。
如果担心死循环，做一个时间上的限制即可，超出时间就抛出错误，或者返回-1 不存在此数，即可。（有限时间内的最好解法）

1 、这个算法不需要公开或者了解 getRandom(x) 内置算法的逻辑。
2 、这个算法基本不会改变 getRandom(x) 内置的概率。
3 、这个算法不需要关心 getRandom(x) 返回的所有值的集合有多大，集合是否包含 0 到 x-1 的所有整数，是有限集合还是无限集合。
4 、这个算法容易让人理解。容易移交。

=================================
让我们设想一个场景：
一家手游公司，做了抽卡系统。
卡池就是 list(n)，list 里面每个下标对应一张卡。
公司设计了一个复杂的抽卡系统。
卡牌里面有 SSR ，SR ，R ，N 等不同卡牌，对应不同权重概率。
调用方法就是 getRandom(n) ，然后会按照设定好的权重概率返回一个卡牌给用户。（全卡池单抽）
-------------------------------------
新上线的时候，卡池只有 10 张卡。
所以 getRandom(9)，大家开心抽卡。
-------------------------------------
1 个月后，版本更新。
卡池有 20 张卡了。
大家就变成了 getRandom(19)，开心抽卡。
-------------------------------------
又过了半个月，画师 W 被爆出美术抄袭，第 14 号卡牌被迫删除下架。
程序大佬将 getRandom(n)内部权重概率调整了下。
外部调用还是 getRandom(19)。但是已经抽不到 list(13)卡牌了，因为权重变为 0 了。
大家开心继续运营。
-------------------------------------
又过了 1 个月，版本更新。加了 10 张卡，外加增加了 10 连抽功能。（全卡池十连抽）
getRandom(29)，继续用起来。
10 连抽？调用 10 次即可。
-------------------------------------
接下来下一个版本要实现 [全卡池不重复十连抽] （不掉落重复卡牌）功能。
该你设计了。

sunrealzhang

31 天前

就每次用 random 函数来根据数组可用元素长度随机取一个下标来找到元素，完了把它和数组最后一个空闲下标元素替换，这时数组可用元素长度-1 ，然后再用 random 函数以此类推着来，取够为止

YsHaNg

31 天前

@abc0def 没提供人也没阻止你自己写呀 jd 没说招调包侠吧

ZZ74

31 天前

参考 Java HashMap 的做法数组+数组
比如 [0 ，101 ）的数组 Arr 分成 5 份，每份数组长度 20 ，Arr_x[i]存是否已经用过。下标 i 是返回的随机数，用长度为的 5 数组 KeyArr 分别对应这个 5 份数组，KeyArr[i]=Arr_x 。
取值的时候采用 hash 算法定位长度为 5 的数组的下标，然后、
1.每一份都有 lastUsedIndex 用 lastUsedIndex+1 来获取。
或者
2.使用 hash 获取定位访问的子数组下标。
如果已经使用过了，或者全部都使用了，这种边界反正大家都懂的。

Knuth

31 天前

很经典的面试题，很经典的算法
附上代码
#include <cstddef>
#include <cstdlib>
#include <iostream>
// 等概率无重复的从 N 个数挑出 M 个数, 输出范围是 0~N-1 ，M < N
using namespace std;

// 1. 无重复 m 个值：i 不同保证无重复，m--控制个数
// 2. 等概率：
// i = 0 时，输出 i 只需 rand() % (n - i) < m,概率=m/n
// i = 1 时，输出 i 有两种情况，0 输出还是没输出，0 输出：m-1/n-1, 0 没输出：m/n-1,综合两者可得(m/n)*(m-1/n-1) + (1-m/n)*(m/n-1)=m/n
void genknuth(int m, int n) {
for (int i = 0; i < n; i++) {
if (rand() % (n - i) < m) {
cout << i << endl;
m--;
}
}
}

int main() {
int m = 8, n = 100;
genknuth(m, n);
return 0;
}

Knuth

31 天前

@Knuth 这个算法是 knuth 大佬提出的（

starwing

31 天前

@Knuth 这个算法很优秀，但它是 O(n)级别的，如果 n 很大但是 m 很小会很慢。我以前搞出一个“模拟打乱算法”是 O(m)级别的，原理是模仿打乱算法，但是不真的做一个 O(n)的数组出来，而是用 hash 表代替“已经打乱过的区域”，只需要 O(m)的空间即可。在 m 很小但是 n 很大的时候会比较优，下面是 Go 的实现：

```golang
// SampleFilter 随机采样[0-N)中的 m 个，排除 f 返回 false 的元素.
func SampleFilter(n uint32, m uint32, f func(uint32) bool) []uint32 {
if n == 0 || m == 0 {
return nil
}
// 如果采样结果比长度还多，就直接顺序返回全部值
if m >= n {
indexes := make([]uint32, 0, n)
for i := uint32(0); i < n; i++ {
if f(i) {
indexes = append(indexes, i)
}
}
return indexes
}
// 否则，做一个虚拟索引映射表（表里不存在的就是原索引），走洗牌算法
indexMap := make(map[uint32]uint32, m)
indexes := make([]uint32, 0, m)
for i := uint32(0); i < n; i++ {
if uint32(len(indexes)) >= m {
return indexes
}
// 先获取一个随机索引的映射
ri := RangeRand(i, n-1)
mappedIdx, ok := indexMap[ri]
if !ok {
mappedIdx = ri
}
// 如果满足要求，就加入到结果中
if f(mappedIdx) {
indexes = append(indexes, mappedIdx)
}
// 在随机位置填入当前位置映射后的索引
indexMap[ri], ok = indexMap[i]
if !ok {
indexMap[ri] = i
}
}
return indexes
}

```