i'd generate unique random numbers between 0 , 1000 never repeat (i.e. 6 doesn't show twice), doesn't resort o(n) search of previous values it. possible?
initialize array of 1001 integers values 0-1000 , set variable, max, current max index of array (starting 1000). pick random number, r, between 0 , max, swap number @ position r number @ position max , return number @ position max. decrement max 1 , continue. when max 0, set max size of array - 1 , start again without need reinitialize array.
update: although came method on own when answered question, after research realize modified version of fisher-yates known durstenfeld-fisher-yates or knuth-fisher-yates. since description may little difficult follow, have provided example below (using 11 elements instead of 1001):
array starts off 11 elements initialized array[n] = n, max starts off @ 10:
+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10| +--+--+--+--+--+--+--+--+--+--+--+ ^ max at each iteration, random number r selected between 0 , max, array[r] , array[max] swapped, new array[max] returned, , max 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, numbers in array have been selected, max == 0, , array elements shuffled:
+--+--+--+--+--+--+--+--+--+--+--+ | 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3| +--+--+--+--+--+--+--+--+--+--+--+ at point, max can reset 10 , process can continue.
Comments
Post a Comment