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.

Retriever

How random is "random"? Do you just need something that looks random to a casual inspection? Something that would pass statistical tests? Cryptographic-strength randomness? – Jungjungfrau

The randomness isn't very important it could even follow some sort of pattern as long it doesn't miss out any numbers. I think I should add that to the list to make clear that no numbers can be missing. – Retriever

You might try "pseudorandom permutation" as a search term: the idea is that apply such a permutation to the fixed sequence 1, 2, 3, ..., to get your pseudorandom sequence. Block ciphers are one possible source of pseudorandom permutations. – Jungjungfrau

@Spektre: The OP says "Without storing an Array, List... of all possible numbers" so that won't work. – Tullius

@Tullius thx I missed it somehow...(comment deleted) – Development

I'm surprised by the close votes; this seems like a well-defined question to me (and @rossum's answer shows it's answerable in practice). – Jungjungfrau

@MarkDickinson I agree with you but may be we lack the insight to the topic which could make this too broad. But even then closing question with upvotes and upvoted answers without any comments when OP clearly is answering additional spec request ... I voted for reopen as this is interesting topic worth preserving... we will see if community agrees – Development

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.

Abingdon

It would be nice if this answer could have some more information or links to practical examples. The wikipedia links are very academic and don't really help someone who has little precursor knowledge and just wants to understand how to solve OP's original question. – Digitalism

The questioner said: "I'm more interested in the approach then the actual implementation." That was why I gave a high-level "approach" answer rather than a detailed implementation answer. – Abingdon

That makes sense, but could you provide some additional information anyway? For the rest of us? :) – Digitalism

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]

Granddaddy