python - 通过替换生成随机(等概率)组合

Question

我想从所有可能的组合中生成一个随机组合 combinations_with_replacement .棘手的一点是，我希望每个可能的结果都具有相同的概率，而不需要生成(甚至不是隐含的)所有可能的结果。

例如:

import itertools
import random

random.choice(list(itertools.combinations_with_replacement(range(4), 2)))

这种方法太慢了(而且占用大量内存)，因为它需要创建所有可能的组合，而我只想要一个。

如果我确定有多少 combinations_with_replacement 并将 random.randrange 与 next 和 itertools 一起使用，这还不错.islice 在 itertools.combinations_with_replacement 上。这不需要生成所有可能的组合(最坏情况除外)。但还是太慢了。

另一方面，recipe mentioned in the itertools documentation速度很快，但并非每个组合都有相同的概率。

Answer 1

嗯，我有点进退两难，因为我找到了一个有效的算法，但我不知道为什么。所以做你想做的事，也许房间里的一些数学家可以计算出概率，但它在经验上是有效的。这个想法是一次选择一个元素，增加选择元素的概率。我怀疑推理必须类似于 reservoir sampling 的推理, 但我没有解决。

from random import choice
from itertools import combinations_with_replacement

population = ["A", "B", "C", "D"]
k = 3

def random_comb(population, k):
    idx = []
    indices = list(range(len(population)))
    for _ in range(k):
        idx.append(choice(indices))
        indices.append(idx[-1])
    return tuple(population[i] for i in sorted(idx))

combs = list(combinations_with_replacement(population, k))
counts = {c: 0 for c in combs}

for _ in range(100000):
    counts[random_comb(population, k)] += 1

for comb, count in sorted(counts.items()):
    print("".join(comb), count)

输出是 100,000 次运行后每种可能性出现的次数:

AAA 4913
AAB 4917
AAC 5132
AAD 4966
ABB 5027
ABC 4956
ABD 4959
ACC 5022
ACD 5088
ADD 4985
BBB 5060
BBC 5070
BBD 5056
BCC 4897
BCD 5049
BDD 5059
CCC 5024
CCD 5032
CDD 4859
DDD 4929