Jeff Atwood over at Coding Horror has a brilliant post on the The Dangers of Naïveté in basic algorithms, such as the example on random shuffling. It also illustrates a very deep point about randomness, something that anyone who works with monte carlo methods should readily appreciate. It’s not easy transforming a random number in linear space into one in a higher space.
Good article.
FWIW, it’s stuff like this that makes me really appreciate Python. I know that getting random number stuff right is hard, so I just rely on the builtin Python tools. If I’m ever curious, it’s really easy to look at the source and find the “right” way to do things.
Hey B. Beca sent me a link to your blog. Nice.
I have committed this naive sin myself on more than one occasion. What a ruthless failure of intuition. Now that I think about, it kind of make sense that not all permutations are the same ‘edit distance’ from the original permutation so there is some bias in this naive approach.
I wonder if you can rescue the naive algorithm by adding a sufficient number of additional swaps?
