在 Python 中随机迭代（可能）巨大的 space 位序列

Question

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

编辑： 正如评论中所述，这基本上是“从 m 项中随机选择 n 而不选择相同的item twice”之类的问题，以防这个公式让它变得更容易。

理论上，可以通过创建一个包含所有可能性的列表、对其进行洗牌然后从该列表中选择第一个 n 项来解决问题。但是，由于 space 的可能性可以变得任意大，所以这个列表可能会变得很大，以至于无法首先创建它的内存。

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

最好的方法是什么？

Answer 1

TLDR：您可以使用 PRNG 对所有可以转换为给定长度的位向量的数字进行无冲突遍历。将其用于 select m 数字，然后根据需要将它们转换为目标 space。

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映射，我们可以将问题视为“选择m范围外的数字[0,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

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

恰好，这就是带有 full period does. One such generator class that is simple to implement for arbitrary n=2**N (i.e. length of bit vectors) are the linear congruential generators. This is for example part of the 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

在 Python 中随机迭代（可能）巨大的 space 位序列

Iterate randomly over (possibly) huge space of bit sequences in Python

python

bit