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

[abc0def]

电话面试被问了一个很有趣的问题：给一个函数 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 个数 ，不知道有没有更好的解法。

[liuhuan475]

n 是固定的？还是每次都传不一样的？

[brazz]

如果共享内存，为什么不能先打乱排好顺序，后续需要几个数，弹几个数出来

[opengps]

乱序之后按顺序取用就行了

[liuhuan475]

想到一个解法，用 set 存返回过的数字，生成一个 0-n 的 linkedlist ，生成的时候判断有没有在 set 出现过，出现过则跳过，生成完用 Collections.shuffle()随机打乱一下这个 linkedlist ，然后 remove 前 m 个数字，把这 m 个数字存到 set 里面，并把 m 当作结果返回。时间复杂度 O(n)，空间复杂度 O(n)

[iOCZS]

对 n,n-1...的下标进行随机抽取，这样能保证每次都能取到数

[abc0def]

@brazz 没有提供打乱顺序的功能

[abc0def]

@iOCZS 对，但需要每次把选到的放到最后不然会重复选

[abc0def]

@opengps 没有提供乱序的接口

[fov6363]

将 array shuffle 后，维护一个 readIndex ，每次取 [readIndex, readIndex + m], 然后 readIndex = readIndex + m 。如果 readIndex > array.length ，返回 null 结束

[abc0def]

@liuhuan475 这个问题主要难点是没有提供乱序接口，只有一个函数返回 0 ，n 的一个随机数

[EchoWhale]

不提供接口, 自己实现乱序不就行了?

[cccccccccccccccd]

i = rand(n)
返回 a[i], a[i] = a[n-1]
n -= 1

[EchoWhale]

其实他的本意就是让你用 getRandom 实现自己的乱序函数吧?

每次调用 getRandom, 拿到一个 idx, 放到数组末尾, 数组长度--

[araaaa]

https://chatgpt.com/share/d601e823-ef4f-4047-b539-b885f4d94677

[Maboroshii]

先随机一个数 k, 然后递归 [0, k), [k+1, n) 范围随机下一个 k

[abc0def]

@EchoWhale 对 我感觉是这个意思

[wuyadaxian]

面试的话就要猜猜面试官的意图。
大概率是实现自己的乱序函数。

实际工作中会有几个问题。
1 、getRandom(x) 返回的数是个有限集合吗？有没有可能返回的数的集合非常大或者无限。
2 、此项工作中更注重时间还是空间？
3 、能跑就行。

[ppddtt]

既然不能乱序数据，你可以乱序索引，shuffle(n), 取前 m 个，然后从 m 个索引里面取

[wuyadaxian]

补充一点，还有就是 getRandom(x) 的返回值有可能分布并不是平均分布，比如是正态分布。
而获取正态分布两端极小概率的值本来就需要很长的运行周期，
中间部分的值会经常重复出现。

在不能查看 getRandom(x) 源代码的情况下，如果你又不知道 getRandom(x) 返回的值的集合是不是一个有限集合。
可能会陷入时间和空间都无法预测的情况。

所以实际工作下，代码能跑就行。

[Sawyerhou]

考虑类似#15 的思路呢？

取第 1 个数
a_0 = getRandom(n)

取第 2 个数
a_1 = (a_0 + 1 + getRandom(n-1)) % n

取第 k 个数，
之前已经取了 k-1 个数，
其将(0, n]分为至多 k-1 个区间，
相邻的数合并为一个切割数集合，
不计入区间个数，

这里假设 j 个区间，
记 j 个切割数集合为 a_0, ..., a_{j-1}

取下一个数
i = getRandom(j)
next = (a_i_max + 1 + getRandom(a_{(i+1)%j}_min - a_i_max - 1)) % n

[meilicat]

参考 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]

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

[liuhuan475]

@abc0def 自己打乱一下也不难

[baislsl]

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

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

[poorLi]

洗牌算法了解下

[forty]

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

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

[Lhcfl]

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

[wuyadaxian]

又重新思考了下，楼主说的 [最简单的解法] 才是最好的解法。
如果担心死循环，做一个时间上的限制即可，超出时间就抛出错误，或者返回-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]

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

[YsHaNg]

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

[ZZ74]

参考 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]

很经典的面试题，很经典的算法
附上代码
#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]

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

[starwing]

@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
}

```

[leonshaw]

@Knuth 不太一样，首先，一次调用时 m 是否已知？其次，概率分布是否与次序相关？例如第一次取到 100 的概率是 0.

[weiwoxinyou]

如果只是想要一个伪随机的数，我感觉可以直接用计算机标准时间来实现：
1. 获取 n 的位数 x
2. 获取当前毫秒数
3. 获取当前毫秒数最后 x 位, 转化为整数 y
3. 判断 y 是否在 set, 不在则直接返回，否则重复 1-3
时间复杂度为 O(1), 空间复杂度为 O(m)

[CC11001100]

https://github.com/golang-infrastructure/go-shuffle

[Knuth]

@leonshaw 概率分布和次序无关，只是用数学归纳法证明等概率，至于 m 你看原贴内容

[lindt99cocoa]

@Knuth 这么多回复里只有这个是正确的，这个题的难点不是提出算法，而是给出证明

[paopjian]

@Knuth 你这名字我以为是你提出来的,吓一跳

[mingl0280]

随便猜的：
声明一个数组 result ，长度 m 。
从 n 中弹一个

[mingl0280]

……别人写过了，就是直接写个乱序数组一个一个弹就行了

[leonshaw]

@Knuth 这个算法结果是递增的，要跟次序无关还需要做一次打乱。关于 m 的问题，可能讨论有一些偏差，我指的是原题，而 op “从 n 个数里面随机取 m 个数” 的表述已经和原题不等价。

[fpk5]

读第 i 个数就把 arr[i]跟 arr[i+random(n - i)]交换并输出这个数，i++。无额外空间，时间复杂度取决于 random 。

这个叫 fisher-yates 算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[nativeBoy]

写个数组，然后取走的数字就设置为-1 ，如果发现已经取了，就用算法寻找下一个位置（类似于哈希开放寻址法）

[Sawyerhou]

看来看去，似乎还是 op 的解法相对更优。