Python 必须my_sample = random.sample(range(100), 10)从[0, 100).
假设我已经对n这些数字进行了采样，现在我想在不替换的情况下再采样一个（不包括任何以前采样的n），如何超级有效地这样做？
更新：从“合理有效”更改为“超级有效”（但忽略常数因素）
问问题
24710 次
13 回答
23
如果您事先知道您想要多个不重叠的样本，最简单的方法是random.shuffle()（list(range(100))Python 3 - 可以跳过list()Python 2 中的），然后根据需要剥离切片。
s = list(range(100))
random.shuffle(s)
first_sample = s[-10:]
del s[-10:]
second_sample = s[-10:]
del s[-10:]
# etc
否则@Chronial 的答案相当有效。
于 2013-09-20T16:30:27.660 回答
10
OP给读者的注意事项：请考虑查看最初接受的答案以理解逻辑，然后理解此答案。
Aaaaaand 为了完整起见：这是necromancer's answer的概念，但经过调整，它需要一个禁止数字列表作为输入。这与我之前的答案中的代码相同，但我们forbid在生成数字之前从 构建状态。
- 这是时间
O(f+k)和记忆O(f+k)。显然，这是对forbid（排序/设置）格式没有要求的最快的事情。我认为这在某种程度上使它成为赢家^^。 - 如果
forbid是一个集合，则重复猜测方法与 相比更快O(k⋅n/(n-(f+k)))，O(k)对于f+k不是非常接近，非常接近n。 - 如果
forbid已排序，我的荒谬算法会更快：
import random
def sample_gen(n, forbid):
state = dict()
track = dict()
for (i, o) in enumerate(forbid):
x = track.get(o, o)
t = state.get(n-i-1, n-i-1)
state[x] = t
track[t] = x
state.pop(n-i-1, None)
track.pop(o, None)
del track
for remaining in xrange(n-len(forbid), 0, -1):
i = random.randrange(remaining)
yield state.get(i, i)
state[i] = state.get(remaining - 1, remaining - 1)
state.pop(remaining - 1, None)
用法：
gen = sample_gen(10, [1, 2, 4, 8])
print gen.next()
print gen.next()
print gen.next()
print gen.next()
于 2013-09-25T01:49:01.483 回答
9
捷径
如果抽样的数量比总体少得多，只需抽样，检查它是否被选中，然后重复。这听起来可能很愚蠢，但是您选择相同数字的可能性呈指数衰减，因此它比O(n)您甚至没有选择一小部分数字要快得多。
漫长的道路
Python 使用 Mersenne Twister 作为其 PRNG，这已经足够了。我们可以完全使用其他东西来以可预测的方式生成不重叠的数字。
当和是素数时，二次余数
x² mod p, 是唯一的。2x < pp如果你“翻转”残基，
p - (x² % p)，此时也给出p = 3 mod 4，结果将是剩余的空格。这不是一个非常令人信服的数字分布，因此您可以增加功率，添加一些软糖常数，然后分布就很好了。
首先我们需要生成素数：
from itertools import count
from math import ceil
from random import randrange
def modprime_at_least(number):
if number <= 2:
return 2
number = (number // 4 * 4) + 3
for number in count(number, 4):
if all(number % factor for factor in range(3, ceil(number ** 0.5)+1, 2)):
return number
您可能会担心生成素数的成本。对于 10⁶ 元素，这需要十分之一毫秒。运行[None] * 10**6需要更长的时间，而且由于它只计算一次，这不是一个真正的问题。
此外，该算法不需要素数的精确值。只需要最多比输入数大的常数因子。这可以通过保存值列表并搜索它们来实现。如果您进行线性扫描，那就是O(log number)，如果您进行二进制搜索，则它是O(log number of cached primes). 事实上，如果你使用疾驰，你可以把它降低到O(log log number)，它基本上是恒定的 ( log log googol = 2)。
然后我们实现生成器
def sample_generator(up_to):
prime = modprime_at_least(up_to+1)
# Fudge to make it less predictable
fudge_power = 2**randrange(7, 11)
fudge_constant = randrange(prime//2, prime)
fudge_factor = randrange(prime//2, prime)
def permute(x):
permuted = pow(x, fudge_power, prime)
return permuted if 2*x <= prime else prime - permuted
for x in range(prime):
res = (permute(x) + fudge_constant) % prime
res = permute((res * fudge_factor) % prime)
if res < up_to:
yield res
并检查它是否有效：
set(sample_generator(10000)) ^ set(range(10000))
#>>> set()
现在，关于这个的可爱之处在于，如果你忽略首要性测试，它大约O(√n)是n元素的数量，这个算法有时间复杂度O(k)，k样本大小和O(1)内存使用量在哪里！从技术上讲是这样O(√n + k)，但实际上是这样O(k)。
要求：
您不需要经过验证的 PRNG。这个 PRNG 比线性同余生成器（很流行；Java 使用它）要好得多，但它不像 Mersenne Twister 那样被证明。
您不会首先生成任何具有不同功能的项目。这通过数学而不是检查避免了重复。下一节我将展示如何去除这个限制。
短的方法一定是不够的（
k必须接近n）。如果k只有一半n，就按照我原来的建议去做。
优点：
极大的内存节省。这需要不断的记忆......甚至没有
O(k)！生成下一个项目的恒定时间。这实际上也相当快：它不如内置的 Mersenne Twister 快，但在 2 倍以内。
冷静。
要删除此要求：
您不会首先生成任何具有不同功能的项目。这通过数学而不是检查避免了重复。
我已经在时间和空间复杂度方面做出了最好的算法，这是我之前生成器的简单扩展。
这是纲要（n是数字池的长度，k是“外”键的数量）：
初始化时间O(√n)；O(log log n)对于所有合理的输入
这是我的算法中唯一在算法复杂性方面技术上并不完美的因素，这要归功于O(√n)成本。实际上，这不会有问题，因为预先计算将其归结为O(log log n)非常接近恒定时间。
如果您以任何固定百分比耗尽可迭代对象，则成本是免费摊销的。
这不是一个实际问题。
摊销O(1)密钥生成时间
显然这是无法改进的。
最坏情况下的O(k)密钥生成时间
如果您有从外部生成的密钥，并且只要求它不能是该生成器已经生成的密钥，则这些被称为“外键”。假定外键是完全随机的。因此，任何能够从池中选择项目的函数都可以这样做。
因为可以有任意数量的外键并且它们可以是完全随机的，所以完美算法的最坏情况是O(k).
最坏情况空间复杂度O(k)
如果假定外键是完全独立的，则每个外键代表一个不同的信息项。因此必须存储所有密钥。该算法碰巧在看到密钥时丢弃密钥，因此内存成本将在生成器的生命周期内清除。
算法
嗯，这是我的两种算法。其实很简单：
def sample_generator(up_to, previously_chosen=set(), *, prune=True):
prime = modprime_at_least(up_to+1)
# Fudge to make it less predictable
fudge_power = 2**randrange(7, 11)
fudge_constant = randrange(prime//2, prime)
fudge_factor = randrange(prime//2, prime)
def permute(x):
permuted = pow(x, fudge_power, prime)
return permuted if 2*x <= prime else prime - permuted
for x in range(prime):
res = (permute(x) + fudge_constant) % prime
res = permute((res * fudge_factor) % prime)
if res in previously_chosen:
if prune:
previously_chosen.remove(res)
elif res < up_to:
yield res
更改就像添加一样简单：
if res in previously_chosen:
previously_chosen.remove(res)
您可以previously_chosen随时通过添加到set您传入的来添加。事实上，您也可以从集合中删除以添加回潜在池，尽管这仅在sample_generator尚未产生或跳过它时才有效与prune=False.
所以有。很容易看出它满足了所有的要求，很容易看出要求是绝对的。请注意，如果您没有集合，它仍然可以通过将输入转换为集合来满足最坏的情况，尽管它会增加开销。
测试RNG的质量
从统计学上讲，我开始好奇这个 PRNG 到底有多好。
一些快速搜索使我创建了这三个测试，它们似乎都显示出很好的结果！
首先，一些随机数：
N = 1000000
my_gen = list(sample_generator(N))
target = list(range(N))
random.shuffle(target)
control = list(range(N))
random.shuffle(control)
这些是从0到的 10⁶ 数字的“打乱”列表10⁶-1，一个使用我们有趣的捏造 PRNG，另一个使用 Mersenne Twister 作为基线。三是控制。
这是一个测试，它查看沿线的两个随机数之间的平均距离。将差异与对照进行比较：
from collections import Counter
def birthdat_calc(randoms):
return Counter(abs(r1-r2)//10000 for r1, r2 in zip(randoms, randoms[1:]))
def birthday_compare(randoms_1, randoms_2):
birthday_1 = sorted(birthdat_calc(randoms_1).items())
birthday_2 = sorted(birthdat_calc(randoms_2).items())
return sum(abs(n1 - n2) for (i1, n1), (i2, n2) in zip(birthday_1, birthday_2))
print(birthday_compare(my_gen, target), birthday_compare(control, target))
#>>> 9514 10136
这小于每个的方差。
这是一个测试，它依次接受 5 个数字并查看元素的顺序。它们应该均匀分布在所有 120 个可能的顺序之间。
def permutations_calc(randoms):
permutations = Counter()
for items in zip(*[iter(randoms)]*5):
sorteditems = sorted(items)
permutations[tuple(sorteditems.index(item) for item in items)] += 1
return permutations
def permutations_compare(randoms_1, randoms_2):
permutations_1 = permutations_calc(randoms_1)
permutations_2 = permutations_calc(randoms_2)
keys = sorted(permutations_1.keys() | permutations_2.keys())
return sum(abs(permutations_1[key] - permutations_2[key]) for key in keys)
print(permutations_compare(my_gen, target), permutations_compare(control, target))
#>>> 5324 5368
这再次小于每个的方差。
这是一个测试，看看“运行”有多长时间，又名。连续增加或减少的部分。
def runs_calc(randoms):
runs = Counter()
run = 0
for item in randoms:
if run == 0:
run = 1
elif run == 1:
run = 2
increasing = item > last
else:
if (item > last) == increasing:
run += 1
else:
runs[run] += 1
run = 0
last = item
return runs
def runs_compare(randoms_1, randoms_2):
runs_1 = runs_calc(randoms_1)
runs_2 = runs_calc(randoms_2)
keys = sorted(runs_1.keys() | runs_2.keys())
return sum(abs(runs_1[key] - runs_2[key]) for key in keys)
print(runs_compare(my_gen, target), runs_compare(control, target))
#>>> 1270 975
这里的差异非常大，在我执行的几次处决中，两者的分布似乎是均匀的。因此，此测试通过。
向我提到了一个线性同余生成器，可能“更有成效”。我自己做了一个糟糕的LCG，看看这是否是一个准确的说法。
LCG，AFAICT，就像普通发电机一样，它们不是循环的。因此，我查看的大多数参考资料，又名。维基百科只涵盖了定义时期的内容，而不是如何制作特定时期的强大 LCG。这可能会影响结果。
开始：
from operator import mul
from functools import reduce
# Credit http://stackoverflow.com/a/16996439/1763356
# Meta: Also Tobias Kienzler seems to have credit for my
# edit to the post, what's up with that?
def factors(n):
d = 2
while d**2 <= n:
while not n % d:
yield d
n //= d
d += 1
if n > 1:
yield n
def sample_generator3(up_to):
for modulier in count(up_to):
modulier_factors = set(factors(modulier))
multiplier = reduce(mul, modulier_factors)
if not modulier % 4:
multiplier *= 2
if multiplier < modulier - 1:
multiplier += 1
break
x = randrange(0, up_to)
fudge_constant = random.randrange(0, modulier)
for modfact in modulier_factors:
while not fudge_constant % modfact:
fudge_constant //= modfact
for _ in range(modulier):
if x < up_to:
yield x
x = (x * multiplier + fudge_constant) % modulier
我们不再检查素数，但我们确实需要对因子做一些奇怪的事情。
modulier ≥ up_to > multiplier, fudge_constant > 0a - 1modulier必须能被...中的每个因子整除- ...而
fudge_constant必须与modulier
请注意，这些不是 LCG 的规则，而是具有完整周期的 LCG，这显然等于modulier。
我是这样做的：
modulier至少尝试一次up_to，满足条件时停止- 做一组它的因数，
- 让我们
multiplier成为删除重复项的产品 - 如果
multiplier不小于modulier，继续下一个modulier - 让
fudge_constant是 一个 小于 的 数字modulier, 随机 选择 - 去除其中的
fudge_constant因素
- 做一组它的因数，
这不是一个很好的生成方法，但我不明白为什么它会影响数字的质量，除了低fudge_constants 和multiplier比完美的生成器更常见的事实。
无论如何，结果令人震惊：
print(birthday_compare(lcg, target), birthday_compare(control, target))
#>>> 22532 10650
print(permutations_compare(lcg, target), permutations_compare(control, target))
#>>> 17968 5820
print(runs_compare(lcg, target), runs_compare(control, target))
#>>> 8320 662
总之，我的 RNG 很好，而线性同余生成器不是。考虑到 Java 摆脱了线性同余生成器（尽管它只使用低位），我希望我的版本绰绰有余。
于 2013-09-20T16:27:05.000 回答
9
好的，我们开始吧。这应该是最快的非概率算法。它有 runtime ofO(k⋅log²(s) + f⋅log(f)) ⊂ O(k⋅log²(f+k) + f⋅log(f)))和 space O(k+f)。f是禁止数字的数量，s是最长的禁止数字条纹的长度。对此的期望更为复杂，但显然受f. 如果您假设它s^log₂(s)大于或只是对再次是概率f的事实不满意，您可以将日志部分更改为二等分搜索以获得.sforbidden[pos:]O(k⋅log(f+k) + f⋅log(f))
这里的实际实现是，就像在列表中O(k⋅(k+f)+f⋅log(f))插入一样。这很容易通过用blist sortedlist替换该列表来解决。forbidO(n)
我还添加了一些评论，因为这个算法非常复杂。该lin部分的作用与该部分相同log，但需要s而不是log²(s)时间。
import bisect
import random
def sample(k, end, forbid):
forbidden = sorted(forbid)
out = []
# remove the last block from forbidden if it touches end
for end in reversed(xrange(end+1)):
if len(forbidden) > 0 and forbidden[-1] == end:
del forbidden[-1]
else:
break
for i in xrange(k):
v = random.randrange(end - len(forbidden) + 1)
# increase v by the number of values < v
pos = bisect.bisect(forbidden, v)
v += pos
# this number might also be already taken, find the
# first free spot
##### linear
#while pos < len(forbidden) and forbidden[pos] <=v:
# pos += 1
# v += 1
##### log
while pos < len(forbidden) and forbidden[pos] <= v:
step = 2
# when this is finished, we know that:
# • forbidden[pos + step/2] <= v + step/2
# • forbidden[pos + step] > v + step
# so repeat until (checked by outer loop):
# forbidden[pos + step/2] == v + step/2
while (pos + step <= len(forbidden)) and \
(forbidden[pos + step - 1] <= v + step - 1):
step = step << 1
pos += step >> 1
v += step >> 1
if v == end:
end -= 1
else:
bisect.insort(forbidden, v)
out.append(v)
return out
现在将其与 Veedrac 提出的“hack”（和 python 中的默认实现）进行比较，它有空间O(f+k)和（n/(n-(f+k))是“猜测”的预期数量</a>）时间：
我只是绘制了这个和k=10一个相当大的n=10000（它只会变得更大更极端n）。我不得不说：我实施这个只是因为它看起来是一个有趣的挑战，但即使我也对它的极端程度感到惊讶：
让我们放大看看发生了什么：
是的——你生成的第 9998 个数字的猜测速度更快。请注意，正如您在第一个情节中看到的那样，即使是我的单线也可能更快f/n（但对于 big 仍然有相当可怕的空间要求n）。
把要点带回家：你在这里花时间做的唯一一件事就是生成集合，因为这是fVeedrac 方法中的因素。
所以我希望我在这里的时间没有被浪费，我设法让你相信 Veedrac 的方法是正确的方法。我可以理解为什么概率部分给你带来困扰，但也许想想 hashmaps (= python dicts) 和大量其他算法使用类似方法工作的事实，它们似乎做得很好。
您可能会害怕重复次数的差异。如上所述，这遵循具有 的几何分布p=n-f/n。所以标准偏差（=您“应该期望”结果偏离预期平均值的量）是
这与均值 ( ) 基本相同√f⋅n < √n² = n。
****编辑**：
我刚刚意识到s实际上也是n/(n-(f+k)). 所以我的算法更精确的运行时间是O(k⋅log²(n/(n-(f+k))) + f⋅log(f)). 这很好，因为鉴于上面的图表，它证明了我的直觉，这比O(k⋅log(f+k) + f⋅log(f)). 但请放心，这也不会改变上述结果，因为它f⋅log(f)是运行时中绝对占主导地位的部分。
于 2013-09-21T04:40:54.240 回答
8
好的，最后一次尝试；-) 以改变碱基序列为代价，这不占用额外的空间，并且n每次sample(n)调用所需的时间成正比：
class Sampler(object):
def __init__(self, base):
self.base = base
self.navail = len(base)
def sample(self, n):
from random import randrange
if n < 0:
raise ValueError("n must be >= 0")
if n > self.navail:
raise ValueError("fewer than %s unused remain" % n)
base = self.base
for _ in range(n):
i = randrange(self.navail)
self.navail -= 1
base[i], base[self.navail] = base[self.navail], base[i]
return base[self.navail : self.navail + n]
小司机：
s = Sampler(list(range(100)))
for i in range(9):
print s.sample(10)
print s.sample(1)
print s.sample(1)
实际上，这实现了一个可恢复的，在元素被选择 random.shuffle()后暂停。没有被破坏，而是被置换。nbase
于 2013-09-20T20:08:18.297 回答
7
这是一种不显式构建差异集的方法。但它确实使用了@Veedrac 的“接受/拒绝”逻辑的一种形式。如果您不愿意在进行过程中改变碱基序列，恐怕这是不可避免的：
def sample(n, base, forbidden):
# base is iterable, forbidden is a set.
# Every element of forbidden must be in base.
# forbidden is updated.
from random import random
nusable = len(base) - len(forbidden)
assert nusable >= n
result = []
if n == 0:
return result
for elt in base:
if elt in forbidden:
continue
if nusable * random() < n:
result.append(elt)
forbidden.add(elt)
n -= 1
if n == 0:
return result
nusable -= 1
assert False, "oops!"
这是一个小司机：
base = list(range(100))
forbidden = set()
for i in range(10):
print sample(10, base, forbidden)
于 2013-09-20T17:30:07.013 回答
6
您可以根据Wikipedia 的“Fisher--Yates shuffle#Modern method”实现一个洗牌生成器
def shuffle_gen(src):
""" yields random items from base without repetition. Clobbers `src`. """
for remaining in xrange(len(src), 0, -1):
i = random.randrange(remaining)
yield src[i]
src[i] = src[remaining - 1]
然后可以使用切片itertools.islice：
>>> import itertools
>>> sampler = shuffle_gen(range(100))
>>> sample1 = list(itertools.islice(sampler, 10))
>>> sample1
[37, 1, 51, 82, 83, 12, 31, 56, 15, 92]
>>> sample2 = list(itertools.islice(sampler, 80))
>>> sample2
[79, 66, 65, 23, 63, 14, 30, 38, 41, 3, 47, 42, 22, 11, 91, 16, 58, 20, 96, 32, 76, 55, 59, 53, 94, 88, 21, 9, 90, 75, 74, 29, 48, 28, 0, 89, 46, 70, 60, 73, 71, 72, 93, 24, 34, 26, 99, 97, 39, 17, 86, 52, 44, 40, 49, 77, 8, 61, 18, 87, 13, 78, 62, 25, 36, 7, 84, 2, 6, 81, 10, 80, 45, 57, 5, 64, 33, 95, 43, 68]
>>> sample3 = list(itertools.islice(sampler, 20))
>>> sample3
[85, 19, 54, 27, 35, 4, 98, 50, 67, 69]
于 2013-09-23T16:50:08.513 回答
6
这是我的 Knuth shuffle 版本，最初由Tim Peters发布，由Eric美化，然后由necromancer进行了很好的空间优化。
这是基于 Eric 的版本，因为我确实发现他的代码非常漂亮:)。
import random
def shuffle_gen(n):
# this is used like a range(n) list, but we don’t store
# those entries where state[i] = i.
state = dict()
for remaining in xrange(n, 0, -1):
i = random.randrange(remaining)
yield state.get(i,i)
state[i] = state.get(remaining - 1,remaining - 1)
# Cleanup – we don’t need this information anymore
state.pop(remaining - 1, None)
用法：
out = []
gen = shuffle_gen(100)
for n in range(100):
out.append(gen.next())
print out, len(set(out))
于 2013-09-24T19:22:44.307 回答
5
相当快的单线（O(n + m), n=range,m=old 样本大小）：
next_sample = random.sample(set(range(100)).difference(my_sample), 10)
于 2013-09-20T16:22:04.497 回答
5
编辑：查看下面@TimPeters 和@Chronial 提供的更简洁的版本。一个小的编辑把它推到了顶部。
这是我认为增量采样最有效的解决方案。调用者维护的状态不是先前采样的数字列表，而是包括可供增量采样器使用的字典，以及范围内剩余的数字计数。
下面是一个示范性的实现。与其他解决方案相比：
- 没有循环（没有标准 Python/Veedrac hack；Python impl 和 Veedrac 之间共享信用）
- 时间复杂度为
O(log(number_previously_sampled)) - 空间复杂度是
O(number_previously_sampled)
代码：
import random
def remove (i, n, state):
if i == n - 1:
if i in state:
t = state[i]
del state[i]
return t
else:
return i
else:
if i in state:
t = state[i]
if n - 1 in state:
state[i] = state[n - 1]
del state[n - 1]
else:
state[i] = n - 1
return t
else:
if n - 1 in state:
state[i] = state[n - 1]
del state[n - 1]
else:
state[i] = n - 1
return i
s = dict()
for n in range(100, 0, -1):
print remove(random.randrange(n), n, s)
于 2013-09-24T15:27:52.463 回答
5
这是@necromancer 很酷的解决方案的重写版本。将其包装在一个类中，使其更容易正确使用，并使用更多的dict方法来减少代码行。
from random import randrange
class Sampler:
def __init__(self, n):
self.n = n # number remaining from original range(n)
# i is a key iff i < n and i already returned;
# in that case, state[i] is a value to return
# instead of i.
self.state = dict()
def get(self):
n = self.n
if n <= 0:
raise ValueError("range exhausted")
result = i = randrange(n)
state = self.state
# Most of the fiddling here is just to get
# rid of state[n-1] (if it exists). It's a
# space optimization.
if i == n - 1:
if i in state:
result = state.pop(i)
elif i in state:
result = state[i]
if n - 1 in state:
state[i] = state.pop(n - 1)
else:
state[i] = n - 1
elif n - 1 in state:
state[i] = state.pop(n - 1)
else:
state[i] = n - 1
self.n = n-1
return result
这是一个基本的驱动程序：
s = Sampler(100)
allx = [s.get() for _ in range(100)]
assert sorted(allx) == list(range(100))
from collections import Counter
c = Counter()
for i in range(6000):
s = Sampler(3)
one = tuple(s.get() for _ in range(3))
c[one] += 1
for k, v in sorted(c.items()):
print(k, v)
和样本输出：
(0, 1, 2) 1001
(0, 2, 1) 991
(1, 0, 2) 995
(1, 2, 0) 1044
(2, 0, 1) 950
(2, 1, 0) 1019
通过眼球，该分布很好（如果您持怀疑态度，请进行卡方检验）。这里的一些解决方案没有以相等的概率给出每个排列（即使它们以相等的概率返回 n 的每个 k 子集），所以random.sample()在这方面是不同的。
于 2013-09-24T18:50:43.900 回答
1
令人惊讶的是，这还没有在其中一个核心函数中实现，但这里是干净的版本，它返回采样值和列表而无需替换：
def sample_n_points_without_replacement(n, set_of_points):
sampled_point_indices = random.sample(range(len(set_of_points)), n)
sampled_point_indices.sort(reverse=True)
sampled_points = [set_of_points[sampled_point_index] for sampled_point_index in sampled_point_indices]
for sampled_point_index in sampled_point_indices:
del(set_of_points[sampled_point_index])
return sampled_points, set_of_points
于 2020-02-20T14:52:42.383 回答
0
这是一个旁注：假设您想解决完全相同的采样问题而不在列表上进行替换（我将称之为sample_space），但不是在您尚未采样的元素集上均匀采样，而是给出初始概率分布p，它告诉您对i^th分布元素进行采样的概率，您是否对整个空间进行采样。
然后使用 numpy 的以下实现在数值上是稳定的：
import numpy as np
def iterative_sampler(sample_space, p=None):
"""
Samples elements from a sample space (a list)
with a given probability distribution p (numPy array)
without replacement. If called until StopIteration is raised,
effectively produces a permutation of the sample space.
"""
if p is None:
p = np.array([1/len(sample_space) for _ in sample_space])
try:
assert isinstance(sample_space, list)
assert isinstance(p, np.ndarray)
except AssertionError:
raise TypeError("Required types: \nsample_space: list \np type: np.ndarray")
# Main loop
n = len(sample_space)
idxs_left = list(range(n))
for i in range(n):
idx = np.random.choice(
range(n-i),
p= p[idxs_left] / p[idxs_left].sum()
)
yield sample_space[idxs_left[idx]]
del idxs_left[idx]
短小精悍，我喜欢。让我知道你们的想法！
于 2020-01-16T16:49:36.447 回答