An algorithm for generating 1000 different integers in the range [0.8000]?

Question

Possible duplicate:
How do you efficiently generate a list of K non-repeating integers between 0 and the upper bound of N

What are some alternative methods for generating 1000 different random numbers in the range [0.8000] as opposed to the following:

• naive method: generating a number and checking it is already in the array. O (N ^ 2)
• linear shuffle: generate a sequence from 0 to 8000, shuffle, accept the first 1000. O (n)

Answer 1

You can use partial Fisher-Yates shuffle implemented using swaps. One of the nice features of this algorithm is that if you stop after k swaps, the first k numbers are an arbitrary sample of size k from the complete set.

Answer 2

You can create a list containing numbers from 0 to 8000.

Then the loop 1000 times generates a random number between 0 and the length of the list.

Remove this item from the list and add it to the output list.

By deleting the item, you will make sure that your choice is unique.

 while (outputList.Count < 1000) { index = random.Next(0, inputList.Count); outputList.Add(inputList[index]); inputList.RemoveAt(index); } 

Answer 3

This is from Knuth Art of Programming (via Jon Bentley Programming Pearls) implemented in Python:

 import random # randomly select m numbers from n candidates def random_select(m, n): select = m result = [] for i in xrange(n): if random.randint(0, ni) < select: result.append(i) select -= 1 return result random_select(1000, 8000) 

this will create a list of random numbers in numerical order. It works by iterating over all integers from 0-n (for example, 0-8000) and randomly selecting them with probability (the number of left to choose / the number of remaining candidates). It works in O (n), so don't try it if n is very large compared to m - for example. choosing ten numbers out of a billion. It does not use memory other than a list of results (m) and several local variables, unlike solutions that rely on shuffling a list of length n.

If you want to get the result in random order, then shuffle the list later.

Answer 4

Partial Fisher-Yates, as @Mark suggested with a slight twist to keep swaps along the way.
Thus, it will consume as much memory as the list of O (m) results.
It will also work in O (m), not O (n), like other solutions that list the entire range - so it should not have problems on large ranges.
Thus, you can get the best of both worlds.

 /// <summary> /// Generates unique random numbers /// <remarks> /// Worst case memory usage is O(min((emax-imin)/2, num)) /// </remarks> /// </summary> /// <param name="random">Random source</param> /// <param name="imin">Inclusive lower bound</param> /// <param name="emax">Exclusive upper bound</param> /// <param name="num">Number of integers to generate</param> /// <returns>Sequence of unique random numbers</returns> public static IEnumerable<int> UniqueRandoms( Random random, int imin, int emax, int num) { int dictsize = num; long half = (emax - (long)imin + 1) / 2; if (half < dictsize) dictsize = (int)half; Dictionary<int, int> trans = new Dictionary<int, int>(dictsize); for (int i = 0; i < num; i++) { int current = imin + i; int r = random.Next(current, emax); int right; if (!trans.TryGetValue(r, out right)) { right = r; } int left; if (trans.TryGetValue(current, out left)) { trans.Remove(current); } else { left = current; } if (r > current) { trans[r] = left; } yield return right; } } 

Answer 5

Sorted list without sorting, O (n)

If you want integers to be sorted, I got this answer in another question with a lot of help. You can do this using an exponential variable and thereby avoid any kind . As a result, this is O (n):

From Alok's answer and Dan Dyer's comment, it turns out that using the exponential distribution for a set of deltas gives a uniform distribution of integers in a sequence.

So, you are just starting to generate numbers, and then scale them at the end. Adding 1 to the delta ensures that you will never repeat the value.

 import random,sys,math def genSortedInts(mini,maxi,vals): running = 0 deltas = [random.expovariate(1.0) for i in range(0,vals+1)] floats = [] for d in deltas: running += d floats.append(running) upper = floats.pop() valRange = maxi-mini-(vals-1) ints = [mini+int(f/upper*valRange)+id for id,f in enumerate(floats)] return ints if __name__ == "__main__": vals = 10 maxi = 80 mini = 0 print(genSortedInts(mini,maxi,vals)) 

Note the use of random.expovariate(1.0) , a Python exponential random number generator (very useful!). Here it is called with a value of 1.0 (arg is 1 / mean), but since the script normalizes against the last number in the sequence, the value itself does not matter.

Conclusion (fair bone roll) for 10 values ​​up to 80:

 [3, 5, 10, 16, 25, 37, 41, 45, 57, 70]