Home > OS >  A random generator with non-repeating elements and changing range
A random generator with non-repeating elements and changing range

Time:12-22

I want to implement a random generator so that it is able to generate random number from 0 to n, but unless the range is exhausted, it should not return elements that has been returned. e.g. if the range is from 0 to 7, and the previous generation is 4, then 4 will not appear in the random generation until all integers in 0-7 are returned. Here is what I have so far - I swap the generated element to the front of the array and shrink the range.

Now I have to implement a function to change the range of the random generation while generating and the non-repeat condition still holds after the range has been changed. The function take a lower and upper bound, which indicates the new range and can be less or more than the old range. For example after 4 is returned, I change the range to 2 to 7, then 4 will not appear in the generation after the list 2-7 is exhausted.

I don't know what is the most efficient way of doing so. I tried to make a blacklist and regenerate an array in the range with numbers that are not in the blacklist, but I am having some problems with resetting the array after the list is exhausted.

class RandomGenerator:
    def __init__(self, n):
        self.n = n
        self.start = 0
        self.arr = list(range(n 1))
        
    def generate(self):
        if self.start > self.n:
            self.arr = list(range(n 1))
        
        r = random.randint(self.start, self.n)
        out = self.arr[r]
        
        temp = self.arr[self.start]
        self.arr[self.start] = self.arr[r]
        self.arr[r] = temp
        
        self.start  = 1
        
        return out

CodePudding user response:

For small n, you could generate a list of numbers, randomly shuffle it, then pop elements out of it; when it is exhausted, generate a new source, and repeat.

import random


def get_random_without_repeats(n=8):
    source = []
    while True:
        if not source:
            source = list(range(n))
            random.shuffle(source)
        yield source.pop()
        
        
for elt in get_random_without_repeats():
    print(elt)

You can add more sophisticated logic to regenerate the source after exhaustion, to suit your needs. For instance, the following example shrinks the range of values from the bottom, every time the source is exhausted

import random


def get_random_without_repeats(n=8):
    source = []
    turn = 0
    while True:
        if not source:
            source = list(range(turn, n))
            if not source:
                return StopIteration
            turn  = 1
            random.shuffle(source)
        yield source.pop()
        

for elt in get_random_without_repeats():
    print(elt)

CodePudding user response:

Unless I'm missing something obvious, you could just pull numbers from random.sample endlessly in a generator - they're guaranteed to never repeat, and if you iterate over an endless iterator like itertools.cycle you can have the pool of possible numbers "reset" once you've exhausted all numbers in the given range:

from itertools import islice

def get_numbers(minimum, maximum):
    # minimum and maximum are inclusive
    from itertools import cycle
    from random import sample
    for generator in cycle([sample]):
        yield from generator(range(minimum, maximum 1), k=maximum 1)


print(list(islice(get_numbers(0, 7), 16)))

Output:

[0, 1, 4, 3, 7, 2, 6, 5, 1, 6, 0, 3, 7, 4, 5, 2]
  • Related