3 ms·
Wikipedia gives a few... http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X http://en.wikipedia.org/wiki/Kn
by jcl 17y ago
Wikipedia gives a few...
http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pr...
http://en.wikipedia.org/wiki/Knuth-Bendix_completion_algorithm http://en.wikipedia.org/wiki/Knuth-Bendix_completion_algorit...
There are probably others as well. KMP is well-known and, I believe, commonly implemented for text search. Algorithm X is implemented in his "dancing links" method, and can be used (among other things) to solve Sudoku puzzles.
- 10ren 17y agoThanks, how silly of me: the text search algorithms are some of my favourites. :-(
- paulgb 17y agoI learned of the Fisher-Yates shuffle as the Knuth shuffle, but apparently both names are used for it. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Aron 17y agoI have used an alternate shuffling approach in the past of my own naive creation, which is to go from 1-N items, each pass selecting a random number to swap the current position with. This would not require counting over missing items (those copied to result) on each loop. What is the flaw in this approach I wonder?
- paulgb 17y agoI've used that method too. The flaw is that it is biased; some permutations will be more likely than others. Each shuffle will consume N random numbers between 1 and N (inclusive). This gives a total of N^N equally probable N-tuples of random numbers, all corresponding to exactly one output permutation. But there are only N! possible permutations, so some of the N^N N-tuples must share the same output permutation. Since N! does not usually divide N^N evenly, some permutations must be more probable than others.
- Aron 17y agoAh....clever. thx.