Andrei Alexandrescu: > Given an array of length m, return a range that iterates the array in > random order such that the entire array is visited without going through > the same element more than once. Consume minimal amounts of memory and > time. Baseline solution: allocate an array of indices, shuffle it, then > follow indices stored in the array.
I have faced such problem more than once, and I have tried to solve it in various ways. The faster solution was: - create an array of m bits, set to zero - Use a random generator to generate integer numbers in [0, m-1], if the corresponding big is set, extract another random number, if it's not set then set it, increment a counter, and return the array item that corresponds to the bit. - When about 90% of the bits is set, create an array with the remaining 10% items of the array, shuffle them in place with the usual algorithm by Knuth, and return them. This is faster than more complex alternatives, and doesn't use much memory. (In the recent past I have tried more complex alternatives, like creating a second bitarray, etc, but they are a waste of time). Bye, bearophile
