Unique (non-repeating) random numbers in O(1)?

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.

You can do this:

1. Create a list, 0..1000.
2. Shuffle the list. (See Fisher-Yates shuffle for a good way to do this.)
3. Return numbers in order from the shuffled list.

So this doesn't require a search of old values each time, but it still requires O(N) for the initial shuffle. But as Nils pointed out in comments, this is amortised O(1).

Use a Maximal Linear Feedback Shift Register.

It's implementable in a few lines of C and at runtime does little more than a couple test/branches, a little addition and bit shifting. It's not random, but it fools most people.

You could use A Linear Congruential Generator. Where m (the modulus) would be the nearest prime bigger than 1000. When you get a number out of the range, just get the next one. The sequence will only repeat once all elements have occurred, and you don't have to use a table. Be aware of the disadvantages of this generator though (including lack of randomness).

You don't even need an array to solve this one.

You need a bitmask and a counter.

Initialize the counter to zero and increment it on successive calls. XOR the counter with the bitmask (randomly selected at startup, or fixed) to generate a psuedorandom number. If you can't have numbers that exceed 1000, don't use a bitmask wider than 9 bits. (In other words, the bitmask is an integer not above 511.)

Make sure that when the counter passes 1000, you reset it to zero. At this time you can select another random bitmask — if you like — to produce the same set of numbers in a different order.

You could use a good pseudo-random number generator with 10 bits and throw away 1001 to 1023 leaving 0 to 1000.

From here we get the design for a 10 bit PRNG..

• 10 bits, feedback polynomial x^10 + x^7 + 1 (period 1023)

• use a Galois LFSR to get fast code

Another posibility:

You can use an array of flags. And take the next one when it;s already chosen.

But, beware after 1000 calls, the function will never end so you must make a safeguard.

Please see my answer at https://stackoverflow.com/a/46807110/8794687

It is one of the simplest algorithms that have average time complexity O(s log s), s denoting the sample size. There are also some links there to hash table algorithms who's complexity is claimed to be O(s).

Someone posted "creating random numbers in excel". I am using this ideal. Create a structure with 2 parts, str.index and str.ran; For 10 random numbers create an array of 10 structures. Set the str.index from 0 to 9 and str.ran to different random number.

for(i=0;i<10; ++i) {
      arr[i].index = i;
      arr[i].ran   = rand();
}

Sort the array on the values in arr[i].ran. The str.index is now in a random order. Below is c code:

#include <stdio.h>
#include <stdlib.h>

struct RanStr { int index; int ran;};
struct RanStr arr[10];

int sort_function(const void *a, const void *b);

int main(int argc, char *argv[])
{
   int cnt, i;

   //seed(125);

   for(i=0;i<10; ++i)
   {
      arr[i].ran   = rand();
      arr[i].index = i;
      printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
   printf("\n===================\n");
   for(i=0;i<10; ++i)
   {
      printf("arr[%d] Random  Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   return 0;
}

int sort_function(const void *a, const void *b)
{
   struct RanStr *a1, *b1;

   a1=(struct RanStr *) a;
   b1=(struct RanStr *) b;

   return( a1->ran - b1->ran );
}