5 ms·
Maybe I'm not being clear. The difference between the right algorithm and the wrong one here is whether or not items that have already been randomly swapped can
by aston 18y ago
Maybe I'm not being clear. The difference between the right algorithm and the wrong one here is whether or not items that have already been randomly swapped can be swapped again. Simply performing n random selections on the list is wrong, and the easiest way to see why it doesn't work is harder math than you probably want to ask people for.
Meanwhile, proving the other answer correct does require an inductive argument (pretty similar to the one that a selection sort works).
If your intuition led you to the right answer, that's cool, but for those who guess wrong, it sucks for them. The question doesn't do a good job of distinguishing between people who are smart and people who aren't because both the right and wrong answers seem pretty right because they're both stochastic. Unfortunately, only one is truly random.
- Tichy 18y agoTo be fair, I don't think I went through as elaborate mathematical considerations as the writer of the article. But even he mentions that he immediately had a bad feeling about the wrong solution, simply because it is doing too much work. The step for me was to move away from the stochastic problem and say "wait a minute, there is a random generator built into my computer already, how can I use it directly". Assuming a horde of mathematicians has already showed that the inbuilt random numbers generator is as good as possible, that way I avoid all the maths issues. And that is a step that seems reasonable to expect from a good programmer. Edit: just read the Knuth Shuffle entry at wikipedia. Happy that I even reinvented the Knuth optimization myself ;-)