Shuffle a Deck of Cards

Shuffling a Deck of Cards using Mersenne Twister.

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>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>QED.</p>
    <p>This shuffle algorithm is therefore as random as the underlying random function and involves one array insertion and the generation of one random number per card.</p>
    <p>Depending on...

CSS

body {
    padding: 8px;
    font-family: Verdana, sans-serif;
}
h2 {
    font-weight: bold;
padding: 1em 0;        
}
p {
    padding: 0 0 1em 0;
}
.red {
color: red;        
}
.card {
    display: inline-block;
    border: thin solid #ccc;
    border-radius: 3px;
    width: 2em;
    height: 3em;
    position: relative;
    margin: 4px;
    box-shadow: 1px 3px 2px rgba(0,0,0,0.5);
}
.value {
    font-size: 10px;
    position: absolute;
    top:1px;
    right:2px;
}
.red, .black {
    font-size: 12px;
    position: absolute;
    top: 1.25em;
    left: 0;
    right: 0;
    display: block;
    text-align: center;
}

JavaScript

/*
  I've wrapped Makoto Matsumoto and Takuji Nishimura's code in a namespace
  so it's better encapsulated. Now you can have multiple random number generators
  and they won't stomp all over eachother's state.
  
  If you want to use this as a substitute for Math.random(), use the random()
  method like so:
  
  var m = new MersenneTwister();
  var randomNumber = m.random();
  
  You can also call the other genrand_{foo}() methods on the instance.

  If you want to use a specific seed in order to get a repeatable random
  sequence, pass an integer into the constructor:

  var m = new MersenneTwister(123);

  and that will always produce the same random sequence.

  Sean McCullough ([email protected])
*/

/* 
   A C-program for MT19937, with initialization improved 2002/1/26.
   Coded by Takuji Nishimura and Makoto Matsumoto.
 
   Before using, initialize the state by using init_genrand(seed)  
   or init_by_array(init_key, key_length).
 
   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
   All rights reserved.                          
 
   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:
 
     1. Redistributions of source code must retain the above copyright
        notice, this list of conditions and the following disclaimer.
 
     2. Redistributions in binary form must reproduce the above copyright
        notice, this list of conditions and the following disclaimer in the
        documentation and/or other materials provided with the distribution.
 
     3. The names of its contributors may not be used to endorse or promote 
        products derived from this software without specific prior written 
        permission.
 
   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   A...