@alvin
well, “obviously” picking 10 unique numbers out of 100 is exactly the same as this shuffle problem, just that you only care about the first 10 (which also means you can stop after 10 steps).
@Tom Dibble
"The WRONG approach would be to pick one in the list at random, then another after it at random, etc, as this would unduly weight the later-in-list items."
Actually no (unless I misunderstood what you meant).
In the first step the probability of selecting a specific item is 1/n. The probability of selecting a specific one in the second step is ((n-1)/n)*(1/(n-1)) = 1/n as well - the first part is the probability of not having it picked in the first step, the second is the probability of picking it now.
In addition this is exactly the same thing that it is done with the “Knuth-Fisher-Yates shuffle algorithm” (never heard that name before).
Btw. one shocking thing about random numbers:
Assume you have a random number generator that gives you equally distributed random numbers in the range [1…n] but you want equally distributed numbers in the range [1…m] where m n and m does not divide n.
Then there is no deterministic algorithm that can do this mapping, and basically the only way is to test if your random number is m and if yes try again (you can optimize this a bit if m n/2).
Which is an algorithm that can not be proven to terminate if you use truly random numbers (though in practice that is not really a problem except in hard-realtime applications)…
This and other things are IMO nicely explained at http://java.sun.com/javase/6/docs/api/java/util/Random.html (see esp. the description of “public int nextInt(int n)”).