从python中的列表生成一个随机的，等概率的组合

Question

假设我有这样的列表：['a','b','c']。我需要从这个列表中随机组合，例如['a','c']。不过，我需要所有组合才具有相同的概率，因此获得['a']的机会应该与获得['b','c']的机会完全相同。我真正的名单是22个元素长，因此列举每一个组合是不可能的。我的第一个想法是使用random.sample，然而它需要你指定元素的数量，它必须随机选择，但概率必须是（在这个组合中元素的数量）/（所有组合中元素的数量）是巨大的数字。有没有更好的方法？这将运行数千次，所以有效的解决方案是值得赞赏的。

Answer 1

有一个非常有效的方法来做到这一点。给定集合的所有组合的集合被称为power set，给定集合的所有子集合的集合。如果集合S包含m个项目，则总共包含2**m个可能的组合，包括空集合和S本身。

所以要从S的幂集中随机选择一个组合，我们只需要从range(2**m)中选择一个随机数n作为幂集的索引，然后生成对应于n的组合。

我们可以通过查看n的二进制展开将索引号n转换为组合。有n个m位。我们将这些比特与S中的项目配对。如果给定位是1，那么为我们的组合选择该项目，如果它是0，我们拒绝该项目。

这是一个简短的演示。

from random import seed, randrange 

seed(42) 

def indexed_combination(seq, n): 
    result = [] 
    for u in seq: 
     if n & 1: 
      result.append(u) 
     n >>= 1 
     if not n: 
      break 
    return result 

print('Testing indexed_combination') 
seq = 'abc' 
for i in range(1 << len(seq)): 
    print(i, ''.join(indexed_combination(seq, i))) 
print() 

def random_combination(seq): 
    n = randrange(1 << len(seq)) 
    return indexed_combination(seq, n) 

print('Testing random_combination') 
seq = 'abcdefghij' 
for i in range(20): 
    print(i, random_combination(seq)) 

输出

Testing indexed_combination 
0 
1 a 
2 b 
3 ab 
4 c 
5 ac 
6 bc 
7 abc 

Testing random_combination 
0 ['c', 'f', 'g', 'h'] 
1 ['a', 'b', 'e', 'f'] 
2 ['a', 'b', 'e', 'f', 'j'] 
3 ['a', 'c', 'e', 'f', 'g', 'h', 'i'] 
4 ['a', 'd', 'g', 'h', 'i'] 
5 ['a', 'c', 'd', 'e', 'i'] 
6 ['a', 'e', 'g', 'h'] 
7 ['b', 'e', 'f', 'h'] 
8 ['f', 'g', 'i', 'j'] 
9 ['a', 'g'] 
10 ['a', 'c', 'd', 'e', 'f'] 
11 ['a', 'b', 'c', 'd', 'e', 'f', 'h'] 
12 ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i'] 
13 ['c', 'd', 'e', 'g', 'h', 'i'] 
14 ['b', 'c', 'e', 'f'] 
15 ['a', 'b', 'c', 'e', 'h', 'i'] 
16 ['a', 'b', 'd', 'e', 'g', 'i', 'j'] 
17 ['a', 'b', 'g', 'h', 'i'] 
18 ['a', 'b', 'c', 'e', 'h', 'i', 'j'] 
19 ['a', 'd', 'e', 'f', 'j'] 

---

我所说的随机函数seed在脚本的具有固定的种子数开始。在开发使用伪随机数的代码时，我发现这很方便，因为当随机数可重现时，它可以更容易地测试和调试代码。在实际应用中，您应该使用系统熵源对radomizer进行播种。您可以通过取消seed呼叫或通过执行seed(None)来轻松完成此操作。如果你想要比标准Mersenee Twister发生器提供的更多的随机性，你可以通过random.SystemRandom类挂钩到系统的随机源。

Answer 2

我将使用combination为n创建一个迭代选择i，然后使用chain来组合所有这样的组合，i等于1到n。组合的总数将为2 ** n - 1，因此我将从0到2 ** n - 2中随机选取一个整数。最后，使用islice从迭代中摘取一个整数。

from itertools import islice, combinations, chain 
from string import ascii_uppercase 

def pickcomb(i): 
    n = len(i) 
    allcomb = chain(*(combinations(i, j) for j in range(1, n + 1))) 
    k = random.randint(0, 2 ** n - 2) 
    return list(islice(allcomb, k, k + 1))[0] 

pickcomb(ascii_uppercase[:22]) 

('A', 'E', 'F', 'H', 'I', 'K', 'L', 'M', 'O', 'Q', 'S', 'T') 

---

测试一下

我怀疑过大的数字，我们应该看到一个相当均匀分布。我将使用pandas.value_counts。你可以看到我们有正确数量的观察类型并且分布相当均匀。

import pandas as pd 

s = pd.value_counts([pickcomb(ascii_uppercase[:5]) for _ in range(100000)]) 
print(len(s), 2 ** 5 - 1, s, sep='\n\n') 

31 

31 

(A, B, C, D, E) 3329 
(A, D)    3320 
(C, D)    3301 
(A, D, E)   3277 
(D, E)    3276 
(B, C, D)   3270 
(A, E)    3268 
(A, B)    3258 
(C, E)    3251 
(A, B, C)   3250 
(A, B, C, E)  3248 
(C, D, E)   3245 
(A, C)    3245 
(D,)    3241 
(C,)    3234 
(A, B, D)   3227 
(A, C, E)   3220 
(B, D, E)   3215 
(A, B, E)   3213 
(B, C, E)   3213 
(B, C, D, E)  3213 
(A, C, D)   3211 
(B, E)    3194 
(B, C)    3193 
(A, B, D, E)  3185 
(A, B, C, D)  3174 
(A, C, D, E)  3158 
(E,)    3151 
(B,)    3150 
(B, D)    3148 
(A,)    3122 
dtype: int64