Shuffling a deck of cards

Very simple and elegant shuffling algorithm with proof of randomness.

by Tonio Loewald

HTML

<h2>Shuffled Deck Sample</h2>
<p id="output"></p>
<h2>Benchmark Results</h2>
<p id="benchmark"></p>
<h2>Shuffling Algorithm</h2>
<p>Starting with an empty destination deck, we go through the cards in the source deck and randomly insert each in turn into the destination deck. As a nice bonus, the algorithm doesn't damage the source deck.</p>
<h3>Proof of validity by induction.</h3>
<p>True for 0 cards (obvious but unconvincing).</p>
<p>True for 1 cards (ditto).</p>
<p>True for 2 cards:</p>
<p>Assume I place A in deck (it has only one place to go) and then randomly insert B anywhere in the deck:</p>
<p>50/50 chance before or after A. So, proven.</p>
<h4>Inductive Step</h4>
<p>Assume true for N-1 cards:</p>
<p>I randomly place new card (N) in any spot from first (1) to last (Nth). It has a 1/N chance of being in any given spot. </p>
<p>Before insertion it had a 1/(N-1) chance of being in any given spot. What are its chances of being in any spot Q ≤ N now?</p>
<p>Well, there are three possibilities: Q = 1, Q > 1 and Q < N, or Q = N.</p>
    <p>In order for a specified card to be in first position it had to be in first position BEFORE random insertion p = 1/(N-1), and the new card needed to NOT be inserted in first position p = (N-1)/N. Multiply these together (they are independent) and we get 1/N.</p>
    <p>Same argument for last position.</p>
    <p>Now consider a middle position M. It either had to be there before p = 1/(N-1) and NOT moved (N-1-Q)/N, or one position below it p = 1/(N-1) and moved p = (Q-1)/N. So the total probability is 1/(N-1) x (N-1-Q)/N + 1/(N-1) x Q/N, or 1/(N-1) x (N-1-Q+Q)/N, or 1/N.</p>
    <p>QED.</p>
    <p>Therefore if true for the first N-1 cards, it's true for N, and since true for 0, 1, and 2, it is true for all finite (or countable) N. </p>
    <p>This shuffle algorithm is therefore as random as the underlying random function and involves one array insertion per card.</p>
    <p>Depending on implementation, destroying elements in the...

CSS

body {
    font-family: Verdana, sans-serif;
}
h2 {
    font-weight: bold;
padding: 1em 0;        
}
p {
    padding: 0 0 1em 0;
}

JavaScript

function fresh_deck(){
    var deck = [],
       suits = ["♠","♥", "♦", "♣"],
       values = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"];
    
    for( var s in suits ){
       for( var v in values ){
           deck.push( values[v] + suits[s] );
       }
    }
    
    return deck;
}

var deck = fresh_deck();

function shuffle( deck ){
   var shuffled = [];
   for( var c in deck ){
       shuffled.splice( Math.floor( Math.random() * (1 + shuffled.length) ), 0, deck[c] );
   }
   return shuffled;
}

shuffled = shuffle(deck);

$("#output").html( shuffled.join(" ") );

var start = (new Date()).getTime();
for( var i = 0; i < 1000; i++ ){
   var dontcare = shuffle( deck );
}
var elapsed = (new Date()).getTime() - start;
console.log("Shuffle Elapsed time", elapsed);

$("#benchmark").html( "1000 shuffles Elapsed time: " + elapsed + "ms" );