如何在Python中高效地生成M个随机二进制数组？

Question

我想在M个不同的位置计算一个二元函数。二元函数的维数是D，因此计算它的函数空间是指数2^D（也就是说，它的输入都是[0,1]^D“字符串”）。我希望它的计算在M唯一/不同的点上，这些点均匀/随机地分布在输入空间中。如果我愿意，我知道如何生成所有的排列（本质上只是将0或1附加到所有之前已经计算过的排列上）。（伪）代码。但是，这是指数型的，我只需要一个分数M点，而不是全部{}。有没有快速的方法？我想随机生成二进制数组，然后如果发生冲突，尝试另一个值，直到它是唯一的。如：

while i < n:
    b_D = randomly_generate_bit_array_length(D) # simply selects each bit randomly with 1/2 prob of choosing 0 or 1.
    if not b_n in HashTable[b_D]:
        HashTable[b_D] = b_D
        i++

然而，根据我得到的答案，here算法似乎是指数型的。如果我的算法的运行时间只是M，而不是指数依赖于D的东西，有没有更好的方法来实现这一点？在

请注意，在我们有M点之前尝试生成所有置换是不可接受的，因为我需要置换在二进制数组中随机分布。i、 如果我们从[0,0,...,0]开始，然后生成[1,0,...,0]直到得到{}不是我想要的，因为我的大多数数组都以0结尾，我希望得到它们的无偏分布。在

---

要生成所有排列：

^{pr2}$

Answer 1

就像在评论中提到的，如果你使用你的D=256和M=120,000那么你的generate random and filter碰撞实际上是O（MD），因为你根本不会有任何碰撞。在

如果你想要大量的数组，你几乎只有机会发生碰撞。正如您可能从birthday paradox中了解到的那样，您需要大约sqrt（| space |）元素，以便有50%的几率发生任何碰撞。所以对于D=256，您需要询问M=2¹²⁸=340282366920938463463374607431768211456数组。只有50%的机会发生任何碰撞。在

相关新闻：就在几天前the first public SHA-1 collision出版了。这仅仅是160位，许多非常聪明的人花了大量的时间和计算机能力来有意地发现一个碰撞。你真的没有任何实际机会意外地用256个随机位产生碰撞。在