python - 从 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 连接到系统的随机源。类。