Can you create a python generator to provide values over a range in a random order without repetition?

Question

I am unsure if this is one of those problems that is impossible or not, in my mind it seems like it should be possible. Edit - We more or less agree it is impossible to do so randomly, but psuedo-random is possible

Given a range specified by two integers (i.e. n1 ... n2), is it possible to create a python generator that yields a random integer from the range WITHOUT repetitions and WITHOUT loading the list of options into memory (i.e. list(range(n1, n2))).

Expected usage would be something like this:

def random_range_generator(n1, n2):
    ...

gen = random_range_generator(1, 6)

for n in gen:
    print(n)

Output:

I don't think this can be done without some record keeping. Is there a reason you don't want to keep the list in memory? — quamrana, Oct 19 '22 at 15:04
Some good discussion in [this question and associated answers](https://stackoverflow.com/questions/21187131/how-to-use-random-shuffle-on-a-generator-python) but from a design standpoint, it seems like you would either need to yield all the elements and then random select/shuffle, or you'd need to store the already selected elements after yielding to prevent duplication. — G. Anderson, Oct 19 '22 at 15:04
@quamrana purely educational for myself, working on a hobby project on my computer so memory isn't really an issue but I was curious if it could be done. After a lot of investigation this morning I think I agree — Alec Petersen, Oct 19 '22 at 15:07
@G.Anderson That's a great discussion, surprised I didn't find it thank you! — Alec Petersen, Oct 19 '22 at 15:09

score 3 · Answer 1 · answered Oct 19 '22 at 15:11

3

How can we shuffle something?

The Idea:

generate pairs (random integer, the stuff you want shuffled)
sort those pairs by the random integer part
output the list of second parts

unsorted = [(random(), x) for x  in range(n1,n2) ]
sorted = sort(unsorted, key = lambda x : x[0])
result = [p[1] for p in sorted]

Note: I haven't tested this but you get the idea. This is a useful method that can be applied/adapted also to similar problems of reordering one thing, based on the ordering of another list.

answered Oct 19 '22 at 15:11

kutschkem

7,826
3
21
56

That is an interesting pattern, I haven't used that before! I won't mark this as the answer simply because its not a generator and requires the list to exist before randomizing it and outputting the values but I appreciate the response! – Alec Petersen Oct 19 '22 at 15:15

score 3 · Answer 2 · answered Oct 19 '22 at 15:20

3

This is simple enough to do, keeping it in memory. Seems to me impossible otherwise:

import random

def random_range_generator(n1, n2):
    r = list(range(n1, n2))
    random.shuffle(r)
    yield from r

gen = random_range_generator(1, 6)

for n in gen:
    print(n)

answered Oct 19 '22 at 15:20

bvan

169
4

For sure, and I think that is the correct answer. I wonder if there is a way to do it that isn't 'random' but effectively random for casual purposes (mixing values in the range in some known way given a seed value) – Alec Petersen Oct 19 '22 at 15:24
I don't think it would be possible because, at one point of another, the generator would have to be evaluated. For example, when you start returning entries, you evaluate the range generator. Generators can ONLY be evaluated in sequence, until it runs out of things to generate, but there is not guarantee of that (it can never terminate). But at some point, you would have to evaluate the last entry of the range generator. And if you keep track of the positions you already generated (to prevent repetitions), you would be essentially be implementing this list(range) one way or the other. – bvan Oct 19 '22 at 15:34
Well if we implement it like this: ``` def random_gen(n1, n2, seed): for i in range(n1, n2): yield get_random_value(n1, n2, i, seed) ``` The `i` allows us to keep track of our current position and can be used as input to create the value, where `get_random_value` is some mathematical function that given a range `n1 ... n2` , a position in that range `i` and a random `seed` can select a unique value from the range for that index. – Alec Petersen Oct 19 '22 at 15:48
Sorry, apparenlty you can't format code blocks in comments, but I don't think there is a way to do it so it is actually random, or even psuedo-random I guess we would say. You could have it return the next value in the range which would be a very light mixing haha, but I imagine you could come up with an equation that would do a better job. – Alec Petersen Oct 19 '22 at 15:49
1

I got what you meant with your original question, but that would imply you have for example a perfect hash function, that maps one field to another 1:1 perfectly, with randomness. Here is one example with python hash: `[hash(str(n)) % (n2 - n1) + n1 for n in range(n1, n2)]`, that for me produces [4, 1, 3, 3, 5] – bvan Oct 20 '22 at 05:41
yeah that makes a lot of sense – Alec Petersen Oct 20 '22 at 23:50

score 1 · Accepted Answer · answered Jun 19 '23 at 14:12

I thought it was impossible to do this without any kind of recordkeeping. Then I found this stack overflow answer which describes a C++ implementation of a parametrizable sequence that is a covering of the natural numbers but quasi-random.

We create a sequence using a prime number and one of its primitive roots modulo n that visits each number in an interval exactly once. We have to pick our prime number a little larger than the product len(a)*len(b), so we have to account for the cases in which we'd get index errors.

import random
from math import gcd

def next_prime(number):
    if number < 0:
        raise ValueError('Negative numbers can not be primes')
    # Base case
    if number <= 1:
        return 2

    # if even go back 1
    if number % 2 == 0:
        number -= 1
    while True:
        # only odds
        number += 2
        #only need to check up to and including the sqrt
        max_check = int(math.sqrt(number))+2
        # don't need to check even numbers
        for divider in range(3, max_check, 2):
            # if 'divider' divides 'number', then 'number' is not prime
            if number % divider == 0:
                break
        # if the for loop didn't break, then 'number' is prime
        else:
            return number

def is_primitive_root(a, n):
    phi = n - 1
    factors = set()
    for i in range(2, int(phi ** 0.5) + 1):
        if phi % i == 0:
            factors.add(i)
            factors.add(phi // i)
    for factor in factors:
        if pow(a, factor, n) == 1:
            return False
    return True




 
def find_random_primitive_root(n):
    candidates = list(range(2,n))
    random.shuffle(candidates)
    for a in candidates:
        if gcd(a, n) == 1 and is_primitive_root(a, n):
            return a




def advance_state(state, close_prime, root):
    # This walks the entire space without repetition
    state = (state * root) % close_prime
    return state


def sampler(l):
    close_prime = next_prime(l)
    state = root = find_random_primitive_root(close_prime)
    while state > l:
        state = advance_state(state, close_prime, root)
    yield state - 1
    for i in range(l - 1):
        state = advance_state(state, close_prime, root)
        while state > l:
            state = advance_state(state, close_prime, root)
        yield state - 1


def _random_order(sequence):
    sequence = sampler(len(sequence))
    for state in sequence:
        yield state


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

Can you create a python generator to provide values over a range in a random order without repetition?

3 Answers3

Linked