A java list randomizer

This week I came across what seemed like a simple programming problem. From a large list of items I wanted to create a smaller list with random items copied from the larger list. The real world equivalent of would be something like bring me four random records from your CD collection.  Sounds simple? Well, there was an additional requirement on that I put on the solution, and that was that the smaller list should contain no duplicates.

There is a Random class in java that returns pseudorandom numbers. However, there is no guarantee that when calling Random.nextInt() a number of times the same number will not be returned twice.  In other words, the simple strategy filling a small list with elements from the large list picked at random with the help of Random.nextInt() will probably produce a result list when the same element is added twice. Not good enough.

One defense against that problem could be to keep track of which numbers the random generator has returned and simply discard any duplicates. For most cases that strategy is probably efficient, but sometimes it could lead to having to discard a whole bunch of random numbers. Moreover, execution times of such a solution would differ a lot depending on which numbers Random.nextInt() returned.

Another solution would be to copy all of the large list to a temporary list and remove each element taken to the smaller list from the temporary list. That way, no item would be added twice to the result list. However, if the source list is long, say a million entries, creating a temporary list to fetch holding all the million entries just to extract 100 random entries would be inefficient.

The elegant solution to this problem in my mind would instead be to create a list of offsets into the large list as long as the small list. The list of offsets would then be modified to emulate the effect of having a copy of the large list and removing entries from it. If the first entry of the offset list is offset 1, and the second offset also is 1, modify that to 2 instead, the element that would have been at position 1 if the original element at that position was removed.

I wrote a class implementing this solution, Randomizer.java. Feel free to use it or modify it anyway you wish.

Filed under Geeky, Programming | Comment (0)