python - 在Python中随机迭代(可能)巨大的位序列空间

Question

所以我有一个可能的位序列的可变空间，例如所有可能的 64 位序列。可能性空间可以变得任意小或大，但该解决方案应该适用于所有情况(例如，它应该适用于所有 64 位序列以及所有 2 位序列)。现在我想在这个空间上迭代 n 次，每次都获得一个随机位字符串(当然我以前没有遇到过)。

编辑: 正如评论中所述，这基本上是“从 m 项中随机挑选 n 项，而不选择相同的项目两次”类似的问题，以防这个公式使它变得更容易。

理论上，可以通过创建一个包含所有可能性的列表，对其进行打乱，然后选择该列表的前 n 个项目来解决该问题。然而，由于可能性的空间可以变得任意大，因此这个列表可能会变得太大，以至于内存无法首先创建它。

我还考虑过每次随机生成一个位串并将已使用的位串存储在一个集合中 - 但这里也有同样的问题，因为迭代的次数 n 不固定， set 可能会变得过于消耗内存。 n 也有可能与可能性空间一样大，在这种情况下，随机生成在某些时候无论如何都不会真正起作用。

最好的方法是什么？

Answer 1

TLDR:您可以使用 PRNG 对所有可以转换为给定长度的位向量的数字进行无冲突遍历。使用它来选择 m 个数字，然后根据需要将它们转换为目标空间。

import random
from itertools import islice

def lcg_cycle(bits: int, seed=None):
    """Pseudo-randomly cycle through all unsigned integers of at most ``bits``"""
    n = 2**bits
    current = seed if seed is not None else random.randrange(0, n)
    for _ in range(n):  # run one cycle
       current = (5 * current + 1) % n
       yield current

#                                                | n| |m|
print(*(f'{num:012b}' for num in islice(lcg_cycle(12), 4)))
# => 101111000001 101011000110 010111011111 110101011100
print(*(f'{num:012b}' for num in islice(lcg_cycle(12), 4)))
# => 111010111110 100110110111 000010010100 001011100101
print(*(f'{num:03b}' for num in lcg_cycle(2)))
# => 000 001 010 011
print(*(f'{num:03b}' for num in lcg_cycle(2)))
# => 011 000 001 010

可以通过随机移位此固定序列并使用从数字到位的不同转换来引入额外的伪随机性。

---

由于“位序列”和“正数”之间存在许多廉价的 1:1 映射，因此我们可以将问题视为“在 [0 范围内挑选 m 个数字” ,n)”。一种可靠的方法是构建整个范围的一些遍历序列，并选择我们需要的任意数量的值。

例如，对于n=8，我们可以选择遍历序列seq = [0, 5, 6, 7, 2, 3, 1, 4]。然后选择 m=3 数字作为 seq[:3]、seq[1:4] 或类似数字(包括环绕)。创建额外的感知随机性非常简单，例如通过向数字添加偏移量，或更改我们的数字->位映射。

def twisted_bits(num, length: int) -> str:
    """Less obvious int -> bin conversion"""
    bits = f"{num:0{length}b}"      # original "unsigned int" bit pattern
    return bits[1::2] + bits[0::2]  # shuffle odd bits to front

def rand8b():
    """Produce a random sequence of the 8-bit pattern"""
    seq = [0, 5, 6, 7, 2, 3, 1, 4]          # chosen by fair roll of dice!
    offset = random.randrange(0, len(seq))
    for item in seq:
        yield twisted_bits((item + offset) % len(seq), 4)

print(*rand8b())  # 0101 0010 0011 0100 0111 0000 0110 0001
print(*rand8b())  # 0001 0110 0111 0000 0011 0100 0010 0101

现在，这将我们的问题简化为“生成任何遍历序列”。位重整和偏移可能足以将范围用于小位计数，但不适用于首先存在问题的较大位计数。因此，我们需要一个类似的惰性序列来遍历该范围，但以一种看似随机的方式。

恰好，这就是具有 full period 的伪随机数生成器。做。一个这样的生成器类很容易实现任意n=2**N(即位向量的长度)是 linear congruential generator s。例如，这是 CPython dict collision resolution strategy 的一部分.

def lcg_cycle(bits: int, seed=None):
    n = 2**bits
    current = seed if seed is not None else random.randrange(0, n)
    for _ in range(n):
       current = (5 * current + 1) % n
       yield current

# always generates all values from a random starting point
print(set(lcg_cycle(3)))  # {0, 1, 2, 3, 4, 5, 6, 7}
print(set(lcg_cycle(3)))  # {0, 1, 2, 3, 4, 5, 6, 7}

可以使用常量，但 5, 1 应该显得足够随机。

根据需要多少明显的随机性，LCG 本身可能就足够了；对于少数位，其周期可能是可见的。和以前一样，它可以与随机偏移量和非标准 int->bin 映射结合起来，以进一步模糊其遍历。

from itertools import islice

def rand_bits(bits: int, count=None):
    """Produce a pseudo-random sequence of fixed-size bit patterns"""
    n = 2 ** bits
    offset = random.randrange(0, n)
    for item in islice(lcg_cycle(bits), count or n):
        yield twisted_bits((item + offset) % n, bits)

print(*rand_bits(32, 4))
# => 11101010011110010000111100100100 11011100110100110001011011101101 10011000100101010011110111011010 01000011011000000000000001111011
print(*rand_bits(32, 4))
# => 11110000110011011111000001101111 00101100111111000001110011111000 01011001111000101111101110100101 00111010011001010101010100000110
print(*rand_bits(32, 4))
# => 00001101101011111010010110001101 11010111010100110110110111100010 11000111100001100101011110001011 01111000100001001110011111011000