6 ms·
Good Knuth, Bad Knuth
- astine 17y agoI can honestly say that that isn't the algorithm that would have occured to me. In CL, this is the what I would have thought to do: (defun butnth (index list) (append (subseq list 0 index) (subseq list (1+ index)))) (defun shuffle (list) (unless (null list) (let ((index (random (list-length list)))) (cons (nth index list) (shuffle (butnth index list)))))) Building a second sequence by randomly selecting nodes from the old sequnece and inserting them into the new sequence seems more intuitive to me. It certainly works better with lists. If I where working with arays, the OPs method would be more efficient.
- duncanj 17y agoI think you're doing the same thing as the "good" knuth algorithm which, as I read it, always exchanges the random card with the one at the decreasing index from the end of the deck.
- joe_the_user 17y agoInteresting. It makes me realize how much whether one begins with lists which allow cheap insertions or not affects both one's choice of algorithm and one's thinking.
- crux_ 17y agoWon't that explode somewhat performance-wise once you have more than a handful of cards? It looks like something along the lines of O(n^2)...
- astine 17y agoAs it's written I'll blow the call stack before I see a performance decrease. :) Actually, the algorithm is O(n), it's essentially a list reversal with a call to random inserted. In psuedocode: oldlist = [...] newlist = [] if oldlist not empty do x = remove random from oldlist insert x into newlist repeat Of course, I'm ignoring the complexity of 'butnth' in that assesment, but this was just a 'first instinct' sort of deal.
- kmcgivney 17y agoI didn't like the butnth. I get an allergic reaction to append. Blame Ken Tilton. (defun shuffle-in-place (l) (cond ((null l) nil) (t (rotatef (nth 0 l) (nth (random (length l)) l)) (shuffle-in-place (rest l)))) l) (defun shuffle (l) (shuffle-in-place (copy-list l)))
- astine 17y agoBlame Ken Tilton. I do. Always. One could use nconc instead of append, but that's not where the processor cycles are being lost as far as I can tell.
- crux_ 17y agoIt's not O(n): both 'nth' and 'butnth' are themselves O(n), and get called 'n' times. I'm fairly certain you'll end up with O(n^2) unless you introduce mutation. I'm also fairly certain there is no purely functional O(n) algorithm. ;)
- astine 17y agoYou're right of course; I'm not looking very deeply. I'm also fairly certain there is no purely functional O(n) algorithm. (defun nth (index list) (if (zerop index) (first index) (nth (1- index) (rest list))))
- crux_ 17y agoI meant for perfect shuffling, not 'nth'. :) This is for you, since I've already had three today & the brainos in your nth implementation are a strong indication for its prescription: http://www.espressoguide.net/resources/images/articles/A002Image01.jpg http://www.espressoguide.net/resources/images/articles/A002I... Cheers!
- rimantas 17y agoSome nice graphs: http://www.codinghorror.com/blog/archives/001015.html http://www.codinghorror.com/blog/archives/001015.html
- Tichy 17y agoIt annoyed me when I heard that some guys slapped their name on that algorithm (having "invented" it independently for a game). It seems like another of those not patent worthy obvious things. Why is it obvious: because you should realise that there is a random number generator in your programming language. Therefore shuffling is silly. You want to assign the cards to slots determined by the random number generator directly. From there on it is pretty straightforward. </brag>
- scott_s 17y agohttp://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Tichy 17y agoYes? That is what I described - I left the swapping part as an exercise to the reader (since it is already described in the article submission). It seems to be the only logical way (I have not tried to think of another way, though - but none has been mentioned yet on HN, either).
- scott_s 17y agoThey didn't "slap their name on it." Other people refer to it as their algorithm because they came up with it first. It's obvious to you that someone would want an algorithm for a random shuffle of a sequence. It wasn't obvious at the time.
- Tichy 17y agoWhat I was trying to say is that the algorithm is the obvious consequence of wanting to assign a sequence to random places in an array. I wanted it because I was programming a game. I think the same must have happened to many people. Anyway, no biggie - of course the world doesn't end because now the algorithm has a name.
- 17y ago
- allenbrunson 17y agoI just happen to have implemented something like this myself recently, which seems easier to me. here it is: generate a large random number for each card, then sort the list according to the random numbers. Can anybody here poke holes in that one?
- l0stman 17y agoA problem can occur if you're shuffling a large number of cards (greater than the maximum of the random number generator) because each random number should be unique.
- fhars 17y agoIt's O(N * log(N)) instead of O(N). And of course it has the usual problem of generating permutations using a pseudo random number generater: Even for moderately sized collections, the number of permutations is far larger than the number of differnt initialization states of many common PRNGs, so even if an algorithm looks correct, it may not be able to generate all permutations. For example, a 63 bit linear congruential shift generator has 2^63 = 9x10^18 possible sequences, while there are about 52! = 80x10^66 permutations of 52 cards.
- allenbrunson 17y agoi'm not really worried about the complexity. it's plenty fast enough for my needs. but i am worried about getting decent results. i suck at anything that smells like math, but i think you're saying that the distribution of random numbers might not be random enough to get decent results, right? is there some random number generator in a C-like language i should investigate, as opposed to using srand() and rand()?
- fhars 17y agoJust read volume 4 of TAoCP when it appears in print :-). Actually, if your game is not about real money, this problem might be more of an academic curiosity, but there are some algorithms with very long periods, start at one of these pages to look for an algorithm with weaknesses that you can live with: - http://en.wikipedia.org/wiki/Mersenne_twister http://en.wikipedia.org/wiki/Mersenne_twister - http://en.wikipedia.org/wiki/Blum_Blum_Shub http://en.wikipedia.org/wiki/Blum_Blum_Shub - http://en.wikipedia.org/wiki/Pseudorandom_number_generator http://en.wikipedia.org/wiki/Pseudorandom_number_generator
- fhars 17y agoAs far as I can tell, the "correct" shuffle in that post is wrong, int(rand() * $i) is always smaller than $i, so it will never generate a permutation where an element stays at the same position. It is obvious from the numbers, too: the loop goes from $length - 1 to 1, so it has $length - 1 iterations, in the first iteration there are $length - 1 possible values for $r, in the second $length - 2, and the last iteration will always swap elements 0 and 1, for a total of (N-1)! different paths through the program, which are clearly not sufficient to generate N! different permutations. [Edit: I had an off-by-one in my calculations, too. I hope it is correct now.] [Edit: Actually, there still is an error in the first sentence: the algoritm will never leave the current element in its place, so the only element that is guaranteed not to stay at the same position is the last one. Run this: for my $i (1..1000000) { my @a = (1..10); my @b = shuffle(@a); if ($b[10] == 10) { die "Criticism is wrong $i"; } } ]
- fhars 17y agoAfter a good night's sleep I see that my second edit is in fact wrong and my intuition in the first sentence was right (and the code in my edit fell victim to the same off-by-one as the code in the article). Final proof: for my $i (1..1000000) { my @a = (0..10); my @b = shuffle(@a); for $j (0..10) { if ($b[$j] == $j) { die "Criticism is wrong $i"; } } }
- deleted 17y ago[deleted]
- jrockway 17y agoThe best way to get this right in Perl: use List::Util qw(shuffle); shuffle(@list);
- astine 17y agoBut that misses the point of the exercise. :)
- rflrob 17y agoSo presumably if the naive interpretation is wrong, then the bias should be predictable. Any ideas how to go about determining which permutations are more likely than they ought to be?
- songism 17y agoThis is how python's shuffle works: def shuffle(x): for i in reversed(xrange(1, len(x))): j = int(random() * (i+1)) x[i], x[j] = x[j], x[i] In the first loop the last element in the list 'x' has a chance to be exchanged with itself or any of the other elements. Then the second to last element has a chance to be exchanged with itself or any other element. All the way down to the second to last element, which has the chance to be exchanged with itself or the first element. This is exactly how the good Knuth shuffle algorithm works, right?
- thisrod 17y agoI'm surprised that the median job candidate gets that wrong. It isn't an especially hard question, and I would have assumed professional programers had a pretty good instinct for combinatorics.