CODEWITHSUNDEEP
python
Kevin
Kevin

Reputation: 155

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

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:

4
1
5
3
2

Upvotes: 2

Views: 209

Answers (3)

Sebastian Wozny
Sebastian Wozny

Reputation: 17506

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]

Upvotes: 2

bvan
bvan

Reputation: 179

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)

Upvotes: 4

kutschkem
kutschkem

Reputation: 8163

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.

Upvotes: 3

Related Questions