Unique non-repeating random numbers in O1

Generating unique (non-repeating) random numbers in O(1) is a fascinating challenge in computer science, often sparking debate among developers and researchers. While truly achieving O(1) for generating an entire sequence of unique random numbers from an arbitrary range is generally not feasible without significant pre-computation or specific constraints, the concept holds critical importance for optimizing various algorithms. Understanding the nuances of “O(1)” in this context requires a deep dive into data structures, algorithmic complexity, and the practical trade-offs involved in random number generation. This article explores strategies and conditions under which we can approach or simulate constant-time retrieval of unique random numbers, providing clarity on a topic that often leads to misconceptions.

Understanding O(1) and Unique Random Number Generation

In computational complexity, O(1) signifies constant time complexity, meaning an operation takes the same amount of time regardless of the input size. For instance, accessing an element in an array by index is an O(1) operation. When discussing unique (non-repeating) random numbers in O(1), the core question is whether we can reliably obtain the next unique random number in constant time, given a predefined range or set, without consuming more time as more numbers are generated.

True generation of a completely fresh, unique random number from a potentially infinite or very large range in O(1) is impractical. This is because checking for uniqueness against all previously generated numbers would, at best, involve a data structure lookup which might be O(1) on average (like a hash set), but the generation itself would likely involve trial-and-error, which isn’t O(1). The common interpretation for achieving “O(1) unique random numbers” usually refers to retrieving the next unique number from a pre-established, finite pool of numbers in constant time, after an initial setup phase that might be O(N).

Consider a scenario where you need to draw unique lottery numbers from a specific range. If you draw one number, then another, and so on, each subsequent draw must be unique. The efficiency of this process is paramount in applications like simulations, card games, or secure token generation. The challenge lies in ensuring both randomness and uniqueness without incurring prohibitive performance costs, especially as the number of required unique values increases. Achieving constant-time retrieval typically involves modifying the underlying data structure from which numbers are drawn.

Techniques for Approaching O(1) Unique Random Number Retrieval

While strict O(1) generation for any range is a myth, there are highly efficient methods for obtaining unique random numbers in effectively constant time after an initial setup. The most prominent of these involves pre-processing a list of numbers and then drawing from it.

Fisher-Yates Shuffle for Permutations

The Fisher-Yates shuffle is a highly effective algorithm for generating a random permutation of a finite set of numbers. Once an array of numbers (e.g., 1 to N) is shuffled, you can simply iterate through the array to get unique random numbers in O(1) per retrieval. The initial shuffle itself takes O(N) time, where N is the size of the set. However, after this one-time cost, each subsequent retrieval is merely an array access, which is O(1).

Initialize a list: Create an array or list containing all the numbers in your desired range (e.g., 0 to 99 for 100 unique numbers).
Perform Fisher-Yates Shuffle: Iterate from the last element down to the first. In each iteration, swap the current element with a randomly chosen element from the unshuffled part of the list.
Retrieve in O(1): Once shuffled, simply pop elements from the end of the array or iterate through it. Each retrieval takes O(1) time.

This method is excellent when you need a significant portion, or all, of the unique numbers from a defined range. For example, in a card game, you shuffle a deck (an O(N) operation) and then draw cards (O(1) per card). This approach provides a practical solution for obtaining unique (non-repeating) random numbers in O(1) for individual retrievals.

Optimizing for Sparse Unique Selections

What if you only need a few unique random numbers from a very large range, and an O(N) pre-shuffle is too costly? This is where alternative strategies come into play, often leveraging hash tables for efficient uniqueness checks, though strict O(1) generation per number remains elusive.

For scenarios requiring only a small subset of unique numbers from a vast range, generating a random number and then checking its uniqueness in a hash set ( Question & Answer :

I’d like to generate unique random numbers between 0 and 1000 that never repeat (i.e. 6 doesn’t show up twice), but that doesn’t resort to something like an O(N) search of previous values to do it. Is this possible?

Initialize an array of 1001 integers with the values 0-1000 and set a variable, max, to the current max index of the array (starting with 1000). Pick a random number, r, between 0 and max, swap the number at the position r with the number at position max and return the number now at position max. Decrement max by 1 and continue. When max is 0, set max back to the size of the array - 1 and start again without the need to reinitialize the array.

Update: Although I came up with this method on my own when I answered the question, after some research I realize this is a modified version of Fisher-Yates known as Durstenfeld-Fisher-Yates or Knuth-Fisher-Yates. Since the description may be a little difficult to follow, I have provided an example below (using 11 elements instead of 1001):

Array starts off with 11 elements initialized to array[n] = n, max starts off at 10:

+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10| +--+--+--+--+--+--+--+--+--+--+--+ ^ max

At each iteration, a random number r is selected between 0 and max, array[r] and array[max] are swapped, the new array[max] is returned, and max is decremented:

max = 10, r = 3 +--------------------+ v v +--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3| +--+--+--+--+--+--+--+--+--+--+--+ max = 9, r = 7 +-----+ v v +--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3| +--+--+--+--+--+--+--+--+--+--+--+ max = 8, r = 1 +--------------------+ v v +--+--+--+--+--+--+--+--+--+--+--+ | 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3| +--+--+--+--+--+--+--+--+--+--+--+ max = 7, r = 5 +-----+ v v +--+--+--+--+--+--+--+--+--+--+--+ | 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3| +--+--+--+--+--+--+--+--+--+--+--+ ...

After 11 iterations, all numbers in the array have been selected, max == 0, and the array elements are shuffled:

+--+--+--+--+--+--+--+--+--+--+--+ | 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3| +--+--+--+--+--+--+--+--+--+--+--+

At this point, max can be reset to 10 and the process can continue.