Generating a shuffled range in python-CodePudding

I need to generate (iterator) a random sequence of 32 bit integers with absolutely no repeats. The naive solutions to this problem don't work for me because of the massive sizes involved, for instance I can't use random.shuffle(range(...)) because that requires loading the very large range into memory, and I can't check every new value for a previous appearance and reroll if found because that would require keeping all previous items in memory.

Is there an algorithm for generating non repeating random numbers in a range?

CodePudding user response：

If you need a relatively small number of unique numbers, random.sample would be perfect here. The documentation gives a relevant example for your use-case:

To choose a sample from a range of integers, use a range() object as an argument. This is especially fast and space efficient for sampling from a large population: sample(range(10000000), k=60).

So if you want, let's say, 1000 unique 32 bit numbers, you could do:

random.sample(range(1 << 32), k=1000)

CodePudding user response：

You can start with a randomly chosen number and then during each subsequent step you can flip a different combination of bits of that original number. A single bit flip can be achieved by using XOR (^) with a number that has a 1 bit at the desired position. There are 2**32 possible bit flip combinations since this is the number of distinct 32-bit integers. So the different bit flip masks are the integers from 0 to 2**32-1 themselves and you can simply iterate over the corresponding range:

import random

def generate(n=32):
    number = random.randrange(2**n)
    for i in range(2**n):
        yield number ^ i

Using the same principle but improving the random stream by adding recursion for the masks and a variable increment larger than 1:

import itertools as it
import random


PRIMES = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223]


def generate(n, *, depth=25, d=0):
    number = random.randrange(n)
    increment = random.choice(PRIMES)  # choose a number coprime to `n`
    if d < depth:
        masks = generate(n, depth=depth, d=d 1)
    else:
        masks = it.accumulate(it.repeat(increment, n-1))
    yield number
    for i in masks:
        yield number ^ (i % n)


for p in range(4, 10):
    n = 2**p
    assert set(generate(n)) == set(range(n))

CodePudding user response：

Encryption is a one-to-one process, so if the inputs are all unique then the outputs must also be unique. Hence if you encrypt the numbers 0, 1, 2, ... you will get a sequence of unique outputs in random order. For 32 bits you will need a 32-bit block cipher. You will need to keep the same key for as long as you want no repetitions. All you will need to store is the key and where you have got to in the range 0..2^32.

Unfortunately, 32 bits is not a common block size since it is too small to be cryptographically secure. Hasty Pudding is one cipher that allows a 32 bit block size. Alternatively is is possible to write your own 32 bit Feistel cipher reasonably easily. For randomness, four or six rounds will be sufficient.