All numbers in a given range, but random order
Let's say I want to generate all integers from 1 to 1000 in random order. But...
- No numbers are generated more than once
- Without saving array, list ... all possible numbers
- Without saving the already generated numbers.
- Without any numbers at the end.
I think it should be impossible, but maybe I just don't think about the right solution.
I would like to use it in C #, but I'm more interested in the assertion and then the actual implementation.
source to share
Encryption. Encryption is a one-to-one mapping between two sets. If the two sets are the same, then it is the permutation indicated by the encryption key. Write / find encryption that maps {0, 1000} to itself. Read Format Save Encryption (FPE) to help you here.
To generate random order, simply encrypt the numbers 0, 1, 2, ... in order. You don't need to store them, just keep track of how far you've come through the list.
As a practical matter, the numbers in {0, 1023} would be easier to deal with as it would be a block cipher with a block size of 10 bits and you could write a simple Feistel cipher to generate your numbers. You might want to do this and just re-encrypt numbers above 1000 - FPE pedestrian crossing method.
source to share
If randomness is not a major concern, you can use a linear congruential generator . Since the LCG will not generate maximum length sequences when the modulus is prime, you will need to select the larger modulus (the next max power of 2 would be the obvious choice) and skip any values outside the required range.
I'm afraid C # isn't actually my thing, but hopefully the next Python is self-explanatory. To generate sequences in very small ranges, a little tweaking is required:
# 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]
source to share