All numbers in a given range but random order

Question

Let's say I want to generate all integers from 1-1000 in a random order. But...

• No numbers are generated more then once
• Without storing an Array, List... of all possible numbers
• Without storing the already generated numbers.
• Without missing any numbers in the end.

I think that should be impossible but maybe I'm just not thinking about the right solution.

I would like to use it in C# but I'm more interested in the approche then the actual implementation.

Answer 1

Encryption. An encryption is a one-to-one mapping between two sets. If the two sets are the same, then it is a permutation specified by the encryption key. Write/find an encryption that maps {0, 1000} onto itself. Read up on Format Preserving Encryption (FPE) to help you here.

To generate the random order just encrypt the numbers 0, 1, 2, ... in order. You don't need to store them, just keep track of how far you have got through the list.

From a practical point of view, numbers in {0, 1023} would be easier to deal with as that would be a block cipher with a 10 bit block size, and you could write a simple Feistel cipher to generate your numbers. You might want to do that anyway, and just re-encrypt numbers above 1000 -- the cycle walking method of FPE.

Answer 2

If randomness isn't a major concern, you could use a linear congruential generator. Since an LCG won't produce a maximal length sequences when the modulus is a prime number, you would need to choose a larger modulus (the next highest power of 2 would be an obvious choice) and skip any values outside the required range.

I'm afraid C# isn't really my thing, but hopefully the following Python is self-explanatory. It will need a bit of tweaking if you want to generate sequences over very small ranges:

# randint(a, b) returns a random integer in the range (a..b) (inclusive)
from random import randint

def lcg_params(u, v):
    # Generate parameters for an LCG that produces a maximal length sequence
    # of numbers in the range (u..v)
    diff = v - u
    if diff < 4:
         raise ValueError("Sorry, range must be at least 4.")
    m = 2 ** diff.bit_length()              # Modulus
    a = (randint(1, (m >> 2) - 1) * 4) + 1  # Random odd integer, (a-1) divisible by 4
    c = randint(3, m) | 1                   # Any odd integer will do
    return (m, a, c, u, diff + 1)

def generate_pseudorandom_sequence(rmin, rmax):
    (m, a, c, offset, seqlength) = lcg_params(rmin, rmax)
    x = 1         # Start with a seed value of 1
    result = []   # Create empty list for output values
    for i in range(seqlength):
        # To generate numbers on the fly without storing them in an array,
        # just run the following while loop to fetch a new number
        while True:
            x = (x * a + c) % m             # Iterate LCG until we get a value in the
            if x < seqlength: break         # required range
        result.append(x + offset)           # Add this value to the list
    return result

Example:

>>> generate_pseudorandom_sequence(1, 20)
[4, 6, 8, 1, 10, 3, 12, 5, 14, 7, 16, 9, 18, 11, 20, 13, 15, 17, 19, 2]