python - 在 Python 中随机选择所有组合的子集

Question

当 n 很小时，我可以构造一个 n 长度二进制值的所有组合列表 itertools.list(product([0, 1], repeat=n))。

1000
0100
0110
1001
 .
 .
 .

当 n 很大时，如何在不首先构建大量组合列表的情况下随机选择上述列表的子集？

假设我想在 n = 30(总共 2^30 个组合)时随机选择 100 万个组合而不进行替换

我查看了 itertools http://docs.python.org/2/library/itertools.html#recipes 的一个扩展函数

def random_product(*args, **kwds):
    "Random selection from itertools.product(*args, **kwds)"
    pools = map(tuple, args) * kwds.get('repeat', 1)
    return tuple(random.choice(pool) for pool in pools)

但它一次只返回一次。在获得 100 万个独特组合之前，我是否应该循环此函数？或者有更好的方法。谢谢!

Answer 1

你可以换个角度思考这个问题。本质上，您只需要 0 和 2^30 之间的 100 万个随机值。

import random

num_selections = 1000000
range = 2 ** 30

def make_set(n, max):
  result = set()
  while(len(result) < n):
    rand = bin(random.randrange(max)) # converting to binary
    result.add(rand)
  return result

s = make_set(num_selections, range)

这在我的机器上运行大约 2 秒。如果 n 大致等于 max，则此方法效率不高。但是 1000000/(2^30) ~= 0.000931，所以它工作正常。

编辑:

@user2285236的解决方案更简洁:

import random
random_group = random.sample(range(2**30), 10**6)
random_group = [bin(x) for x in random_group] # convert all to binary