Linear Shuffle

Shuffle a deck of cards in linear time. Don Knuth suggests attaching a random number to each card and sorting. But that would be O(Nlog N), more than linear.

Knuth's algorithm It's harder to code too. That's why the trick Dave Dodson taught me is so cool. Simply exchange each element of the deck with a random element of the deck. "But some elements will get moved more than once, maybe many times," I protested. "Yes," he said, "but each element is equally likely to appear in any position; what better definition of shuffle?"

It works, of course, and is easy to code in just about any language. But here is the best expression I've ever found.

Which reads, "every element-of deck exchange-with random-element-of deck." I wrote this in Icon. It's my small contribution to Ralph Griswold's Icon book. webpage -- Ward Cunningham

In fact, Don Knuth provides the correct form of this algorithm, as noted later on this page. This is in Volume 2 of The Art Of Computer Programming. -- Brett Neumeier

See also Linear Shuffle Summary

The algorithm performs 3 random swaps. For each random swap, there are 3 possible outcomes. So there are 27 equally likely outcomes. These 27 possibilities cannot be mapped on the 6 orderings, so that each is equally likely, because 27 is not a multiple of 6. Some ordering must be (marginally) favored over others, with respect to the initial ordering.

The technique is a good choice in most settings, but it is not truly random. The distribution is as fair as it can be. In this case there are three "favored" combinations with probability 5/27 and three "disfavored" ones with probability 4/27. Which are favored depends on how the random number generator is mapped to the index selection. Here's one possible result:

Note that for a deck as small as three, a favored combination has a probability that is 25% better than a disfavored ones. And, e.g., b lands in the first position 25% more often than in third.

It is not hard to write a linear shuffle which produces every possible ordering with an equal probability (assuming a good random number generator).

I'll write it in C, since that is what I know best:

The idea is to partition the deck into shuffled and unshuffled sections. The shuffled cards are cards[x], where x < i. Unshuffled cards are cards[x], where x > i. Then, just randomly pick a card from the unshuffled section and add it to the top of the shuffled section.

This is still linear, and as far as I can tell, just requires one additional subtract per loop iteration. It's interesting to compare these statistics to a Hand Shuffle. -- Don Dodson

Forgive me, but Linear Shuffle sounds like a great name for a dance step for line dancing. Imagine applying the algorithm of Don Dodson to a group of dancers in a row, each dancer's movement dictated by the outcome of each iteration of the loop. All we need now is a diagram of the footwork! The Linear Shuffle consists of two basic moves: the Unshuffled Shuffle and the Shuffled Shuffle. Dancers use the steps to either remain in place, or to migrate to the top of the shuffled section of the line dance. Sounds like a PLoP activity. -- Don Olson

Well, I did the math last night and confirmed Tom Cargill's analysis of my algorithm. Working it out made it clear to me what was going wrong. It sure looks like Don Dodson's enhancement fixes the problem. Anyway, I coded up both versions and ran 27000 trials each using identical Random streams (r). My version ...

tallied up as follows ...

which agrees closely with Tom's prediction. (4/27=4000 and 5/27 = 5000)

Don's modification, which I coded as ...

and tallied as ...

looks pretty even to me.

I think Alistair missed that an element could be exchanged with itself. Those who count alternatives will note that Don's version reduces the number of choices with each iteration creating a total of N! possibilities. -- Ward Cunningham

In the spirit of the original (from above):

A fair Icon Language version:

This also restricts the choice as time goes on; unfortunately, there is no equivalent to the Perl Language splice() in Icon Language; their lists are Double Ended Queues, and elements cannot be inserted or deleted from the center.

The proper algorithm is to exchange the n-th element with a random element in the first n, then decrease n by 1 and repeat the process until n = 1. In Fortran, with random() being a function that returns a random number between 0 and 1, this is:

It would be incorrect for the second line to read

Hope this helps.

These solutions only serve to illustrate that if you have a perfect random number generator, you have no need to 'shuffle' anything; simply extract a random element from your list of elements as needed. The original problem was:

Shuffle a deck of cards in linear time.

"Shuffle" could be more realistically defined in terms of human experience as:

Try doing that in linear time. -- Andy Pierce

See Improving Random Numbers.

With shuffling, you can't get the same item twice. With a perfect random number generator, you can. Unless "perfect" means "each number comes up exactly once" which means "not very random at all." -- Dave Harris

One could use a random number generator, *if* one can "extract" (remove without replacing) a random element in O(1) time. The problem is that most extraction schemes are more like O(N/2) time, where N is the number of elements. (One can probably improve the deletion time, but one also has to be able to efficiently choose a random element. Optimizing both of these seems hard.) -- anon.

On the other hand, modern computers are fast enough for random extraction with small N. I recently used a random-extraction loop in Perl to shuffle 8000+ elements. Approximately 16 million (8000 * (8000/2)/2) 32-bit words were moved as elements were extracted. It took a few seconds on a slowish computer. For a 52-element array the same loop should take a few milliseconds at most. -- anon.

Ah! There's an algorithm lurking behind this page, which you need to know to understand what the page is about. It's something like:

In other words, pick a card at random and add it to the pack if it hasn't already been picked. The bool array gives you removal without replacing of a random element in O(1) time. People really do write things like this; it's obvious and fair. The problem is that when you pick the last card, almost all the cards have already been picked, so your chance of hitting the last free card is 1/52. Which makes this O(N*N) instead of O(N) - decidedly non-linear. Linear Shuffle is about not making this mistake.

That is one way to attempt an optimized (but non-linear time) shuffling. In high-level languages with more array/collection support, it is even easier to write an obviously correct shuffle. Here's a sample in Perl:

The key is that the "splice" command removes the target element from the array. (Each time the while loop executes, @deck contains one less card.) The "push" command then adds that extracted card to the shuffled deck.

This is not a linear algorithm, since "splice" takes O(N) time to execute. (It needs to move all the array items after the splice.) However, the O(N) operation of "splice" is usually implemented with a memory-move primitive which is extremely fast (especially since the entire deck array should fit in the CPU caches). Here are some possible cases:

Worst case:<br>52 * (51/2) = 1326 memory moves in "splice" (the first card of @deck is always chosen, and all other cards need to be moved)

Average case:<br>52 * (51/2)/2 = 663 moves (a card in the middle of @deck is chosen, so half the deck needs to be moved)

Best case:<br>52 * 0 = 0 moves (the last card is always chosen, so no moves are needed)

When I first used this to sort 8000+ elements, I didn't do all the analysis above. I was willing to let the program run for several minutes if necessary - I could use the time to catch up on Recent Changes. I was pleasantly surprised that it was so fast. (The whole operation of reading in 8000 lines of text, shuffling them, and writing them to 16 output files took less than 10 seconds.)

The moral of this story is that the acceptable N for O(N*N) is often big enough for one's application. (Beware if the application's N can grow, however.) -- anon.

After a recent comment, I realized that the linear shuffle was confusing because it combines two optimizations:

The linear-time optimization of extracting a random element, then compacting the array (filling in the hole) in O(1) time.

The space optimization of using the same array for both the initial and shuffled deck.

Here is a modified version of the Perl code which should work in linear time:

(This presumes "splice" does the obvious optimization of replacing rather than deletion and inserting.) The key is splicing in the last element to replace the selected one, rather than just removing the selected element. In this version, instead of moving all the following cards (average (N/2)/2 moves), only the last card is moved into the "hole" left by the selected card. -- anon.

Or, in mildly-obfuscated Perl:

Perl Golf

You don't need to predelare @s, and you can replace $d[$#d] with $d[-1] which is both shorter and slightly more legible!

If you allow the hack of declaring @d to be one larger than you need so you can pop it off straight-away, then you can shorten further to:

How about this to shuffle it in place:

You could also use:

but this suffers from the 4000/5000 split problem from above.

I have this algorithm.

I did a Prolog version of a Linear Shuffle about 6 years ago: archive

You'll find my use of the idea of Linear Shuffle as a way to maintain a collection of sets of items in an array in pages 201 to 203 of Software - Practice and Experience, Volume 7 (1977), entitled "Efficient Storage for Amorphous Data".

-- Dick Botting

How about sublinear shuffling... Here is a bit of Java for a change:

This just does what is described above - however it only shuffles on demand which is an advantage in games like blackjack where the rules call for only a part of the deck to be used. -- Jan Larsen

Finally. Now my computer won't hang when it's trying to shuffle 52 element lists. -- Shameless Sarcastic

{'BCA': 9929, 'CAB': 10025, 'BAC': 10041, 'CBA': 10065, 'ABC': 9947, 'ACB': 9993}

This implements the correct algorithm where some swaps are actually leave-alones. (See above for implementations in other languages.) -- Steve Howell

Or trivially:

Since the random module now includes a shuffle in place component in the latest python distribution. I can't speak for the correctness or the optimalness of implementation though. :) -- Andy Pierce

C++ version:

The STL doc page (www.sgi.com ) states that it runs in linear time and that it's the algorithm described in Knuth volume 2. -- Amit Patel

Original discussion moved to Hand Shuffle -- Bel Torak

If these rand() and random() functions are the standard c library calls, they generate a pseudorandom number in the range 0 to 32767. Performing a modulo on the output of this results in an uneven distribution for almost all modulos. Take mod 10 for example, the contribution of 0-32759 are even, but then 32760 through 32767 boost 0-7 higher than 8 and 9. Similar reasoning applies to any modulo that doesn't evenly divide 32768 (i.e. any non-power-of-2).

<i>Well, of course is is really in range between 0 and RAND_MAX, which happens to be 2147483647 on my system. The same argument still applies, although the larger RAND_MAX is, the smaller the deviation is. More fundamentally, any fixed mapping of 0..RAND_MAX-1 onto 0..9 will be "unfair" in this way, unless RAND_MAX is a multiple of 10. A correct way to get a number between 0 and 10 is the following:</i>

For some reason, which I remember Knuth explains, RNGs create numbers that are more random in the higher bits than in the lower ones. So, i'd write such:

Of course, if your language/library can return a number in a range, it's probably optimized for these things.

If you had a function p(n) which mapped from numbers in the range 0 ... N-1 back onto itself and which was one-to-one (ie was a permutation), then rather than shuffling and dealing, you could count, apply p to the index, and fetch that item from the list. Furthermore, if this function was parameterisable and random(ish), this would even be useful. Such functions can be found in cryptography; DES, for example, is such a function on the set of numbers in the range 0 ... 2**64 - 1, parameterised by a 56-bit key. If you have 256 elements, you might try an offset modular multiplication: p(n) = (((n + 1) * (k + 1)) mod 257) - 1, for some value k in 0...255. There is probably no point to any of this.

Is there some information-theory reason why the fastest shuffle algorithm is O(N), while the fastest sorting algorithm is O(NlogN)? That is, is there a mathematical proof that sorting must be slower than shuffling? --Andy Pierce

Yes. There are N! possible orderings; to distinguish between them you need to do at least log2(N!) comparisons, which is of order N log N. The basic operation in shuffling is moving an item to a particular place in the list, which lets you add log N bits of entropy in a single go. You can think of it as being a little like radix sort.

While the idea is right, the conclusion is not quite, as far as I can tell. I was taught that big-O is a worst-case bound, and (PRNG limitations notwithstanding) there really aren't such bounds on this process - a 1/52 chance never has to occur.

But even in the average case, this method isn't O(N^2). Since there are 2 remaining cards to choose from in the second-last draw, it will take on average N/2 tries to find one - and so on, so the expected running time is O(N + N/2 + ... + N/N), which is clearly seen to be O(N lg N). (Or it's clear to me, anyway. I just looked at the integral of 1/x, knowing it differs from the sum of 1/N by at most a constant.) -- Karl Knechtel

This may be implementation-specific, but I believe there is a bug in the STL implementation of random_shuffle of Microsoft Visual C++ 6. The implementation of <algorithm.h> supplied with VC++6 (dated 1995) has this:

There are two random_shuffle function definitions, with and and without the option to supply your own random-number generator). If this code is tidied up to be legible, it reads:

I believe this iterates too few times.

For example, if you take a vector {1,2} and call random_shuffle(vector.begin(), vector.end()), then you *always* obtain {2,1}. If you shuffle {1,2,3}, you obtain {3,1,2} or {2,3,1} only, and so forth. To implement Don Dodson's algorithm (above), the following seems to give better results:

The code adds a few "std::" namespace handles (but could be written with a "using namespace" call instead).

Rudolf Cardinal (rudolf@pobox.com), 29 July 2003.

I was thinking about this problem and it seems that when shuffling a deck of cards and then comparing the shuffle to the previous deck of cards, there should be, on average, 1 card that matches its previous position in the deck (each card has a 1/52 chance of being in its original position and there are 52 cards).

I created the following Java program to test this out. Notice that the "bad" algorithm does not do a good job (> 2 matches per shuffle), the original suggested algorithm does "too good" of a job (< 0.9 matches per shuffle), and the modify algorithm hits about 1.0 matches per shuffle (for 10,000,000 shuffles):

[14:02] kregan@kregan ->java Shuffle Test

Bad shuffle # matches: 20106808 (2.0106808 per shuffle)

Good shuffle # matches: 8999434 (0.8999434 per shuffle)

Even better shuffle # matches: 10002152 (1.0002152 per shuffle)

Here is the program:

System.out.println("Bad shuffle # matches:<br>" + badShuffleMatchCount +

System.out.println("Good shuffle # matches:<br>" + goodShuffleMatchCount +

System.out.println("Even better shuffle # matches:<br>" +

Kevin Regan (kregan@amazon.com), 1 June 2004

<i>n¡ is the number of shufflings of n items in which none are in the same place as their starting positions. If precisely one card in the pack of 52 is unmoved by a shuffle, the rest can be in any one of 51¡ possible orders, giving a total number of "one-card-unmoved" orderings of 52×51¡. The probability that 52 randomly-shuffled cards ends up in one of these arrangements is therefore 52×51¡/52! = 51¡/51! ≈ 37%. (As the equality shows, this is the probability that after shuffling 51 cards, none of them will be in their original location). As n increases without limit, the probability approaches 1/e.</i>

Why do a linear shuffle? How about constant time shuffle? Look at an interesting solution at blogs.mastergaurav.com

Code inlined for completeness.

}

See original on c2.com