CODEWITHSUNDEEP
performancealgorithmrandomunique
tomKPZ
tomKPZ

Reputation: 837

Unique random number algorithm

I would like an algorithm/function that, given a number N, generates random numbers from 0 to N - 1 in constant time. After the Nth call, the function may do as it pleases. Also, it is important that the algorithm generates the numbers when requested rather than using shuffling, because I may (and in the average case do) not need the full list of numbers. What is the best approach to take?

(optional to read) I thought of having a hash set of numbers, and pulling the numbers out one at a time, but this would require inserting all elements (which I often do not need) into the hash set first... this will not work... Argh

Thanks for any help in advance.

Upvotes: 1

Views: 331

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Modify the Fisher–Yates shuffle by replacing the array with a map that stores only the elements that have been moved. In Python:

import random
class Shuffle:
    def __init__(self, n):
        self.d = {}
        self.n = n
    def generate(self):
        i = random.randrange(self.n)
        self.n -= 1
        di = self.d[i] if i in self.d else i  # idiomatically, self.d.get(i, i)
        dn = self.d[self.n] if self.n in self.d else self.n
        self.d[i] = dn
        self.d[self.n] = di
        return di

The space usage and amortized expected running time is O(1) words per element actually generated. Up to log factors, this is optimal.

Upvotes: 2

Related Questions