Shuffle a deck without local variables [closed]

Question

The object of this puzzle is to take a deck of 52 cards and shuffle it so that each card is in a random position.

Given:

• An array, deck, of 52 distinct integers representing the cards. When you start, deck contains exactly one of each card in some unknown order.
• A function, int rand(min, max), that returns a random integer between ints min and max, inclusive. You can assume that this function is truly random.
• A function, void swap(x, y) that swaps two cards in the deck. If you call swap(x, y), the cards at positions x and y will switch places.

When:

• The program calls shuffle() (or shuffle(deck) or deck.shuffle() or however your implementation likes to run),

Then:

• deck should contain exactly one of each card in perfectly random order.

The Catch:

You can't declare any variables. Call swap and rand as much as you like, but you can't declare any variables of your own. This includes for loop counters--even implicit ones like in a foreach.

Clarifications:

• You can change minor details to suit your chosen language. For example, you can write swap to switch two integers by reference. Changes should be to make this work with your language, not to make the puzzle easier.
• deck can be a global variable, or you can take it in as a parameter.
• You can do anything you want to the contents of deck, but you can't change its length.
• Your cards can be numbered 0-51, 1-52, or anything you like.
• You can write this in any language, but no cheating with your language's built-in shuffle function.
• Yes, you could write the same line 52 times. No one will be impressed.
• Execution time doesn't matter, but true randomness does.
• This isn't really code golf, but feel free to minimize/obfuscate your code.

---

Edit: Boilerplate code and visualizer

If you used .NET or JavaScript, here's some test code you may find useful:

JavaScript:

• Quick-and-dirty JavaScript visualizer, with CoffeeScript source: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
• Runnable version (just paste in your shuffle() function): http://jsfiddle.net/4zxjmy42/

C#:

• ASP.NET visualizer with C# codebehind: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
• Stub with just the swap and rand utility methods: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41

This code sorts and shuffles the deck several thousand times and performs some basic sanity testing: For each shuffle, it verifies that there are exactly 52 cards in the deck with no repeats. Then the visualizer plots the frequency of each card ending up at each place in the deck, displaying a grayscale heat map.

The visualizer's output should look like snow with no apparent pattern. Obviously it can't prove true randomness, but it's a quick and easy way to spot-check. I recommend using it or something like it, because certain mistakes in the shuffling algorithm lead to very recognizable patterns in the output. Here's an example of the output from two implementations, one with a common flaw:

The flawed version does partially shuffle the deck, so might look fine if you examined the array by hand. The visualizer makes it easier to notice a pattern.

Answer 1

Haskell

Here is a point-free implementation. No variables, formal parameters, or explicit recursion. I used lambdabot's @pl ("pointless") refactoring feature quite a bit.

import Data.List
import Control.Applicative
import Control.Monad
import System.Random

shuffle :: [a] -> IO [a]
shuffle = liftM2 (<$>) ((fst .) . foldl' (uncurry ((. flip splitAt) . (.) .
          (`ap` snd) . (. fst) . flip flip tail . (ap .) . flip flip head .
          ((.) .) . (. (++)) . flip . (((.) . (,)) .) . flip (:))) . (,) [])
          (sequence . map (randomRIO . (,) 0 . subtract 1) . reverse .
          enumFromTo 1 . length)

main = print =<< shuffle [1..52]

Here's my test procedure to make sure the numbers were uniformly distributed:

main = print . foldl' (zipWith (+)) (replicate 52 0)
       =<< replicateM 1000 (shuffle [1..52])

Here is the original algorithm:

shuffle :: [a] -> IO [a]
shuffle xs = shuffleWith xs <$>
             sequence [randomRIO (0, i - 1) | i <- reverse [1..length xs]]

shuffleWith :: [a] -> [Int] -> [a]
shuffleWith xs ns = fst $ foldl' f ([], xs) ns where
    f (a,b) n = (x:a, xs++ys) where
        (xs, x:ys) = splitAt n b

Answer 2

JavaScript

I believe this is the intended form of solution, I use the card in position 0 to keep track of progress, only shuffling the cards that have already been used as counter, this achieves the standard 52! permutations with a perfect equal distribution. The procedure is complicated by XOR swap not allowing that an element is swapped by itself.

Edit: I built in a sorting that sorts each element into place just before it is used, thus allowing this to work with an unsorted array. I also dropped recursive calling in favour of a while loop.

deck=[]
for(a=0;a<52;a++){
    deck[a]=a
}
function swap(a,b){
    deck[a]=deck[b]^deck[a]
    deck[b]=deck[b]^deck[a]
    deck[a]=deck[b]^deck[a]
}
function rand(a,b){
    return Math.floor(Math.random()*(1+b-a))+a
}
function shuffle(){
    while(deck[0]!=0){ //Sort 0 into element 0
        swap(0,deck[0])
    }
    while(deck[0]<51){ //Run 51 times
        while(deck[deck[0]+1]!=deck[0]+1){ //Sort element deck[0]+1 into position deck[0]+1
            swap(deck[deck[0]+1],deck[0]+1)
        }
        swap(0,deck[0]+1) //Swap element deck[0]+1 into position 0, thus increasing the value of deck[0] by 1
        if(rand(0,deck[0]-1)){ //Swap the element at position deck[0] to a random position in the range 1 to deck[0]
            swap(deck[0],rand(1,deck[0]-1))
        }
    }
    if(rand(0,51)){ //Swap the element at position 0 to a random position
        swap(0,rand(1,51))
    }
}
for(c=0;c<100;c++){
    shuffle()
    document.write(deck+"<br>")
}

Answer 3

J

Ignoring that deck is a variable, there's the obvious...

52 ? 52

Of course, if you really want a function, there's this, which will work even if you forget to remove the jokers (or try to shuffle something other than cards).

{~ (# ? #)

So that...

shuffle =: {~ (# ? #)
deck =: i. 52
shuffle deck

This is probably outside the intent of the question, which would be to implement the shuffle yourself from rand (?). I might do that later when I'm not supposed to be working.

Explanation

Explanation of 52 ? 52:

• x ? y is x random unique items from y.

Explanation of {~ (# ? #) is harder because of forks and hooks. Basically, it is the same as shuffle =: 3 : '((# y) ? (# y)) { y', which has one implicit argument (y).

• # y gives the length of y
• This gives 52 ? 52 like before, which is a random permutation of 0..51
• x { y is the item of y in index x, or (in this case) items in the indexes in x.
• This lets you shuffle whatever is passed in, not just integers.

See J Vocabulary for details of operators, though the syntax and semantics are quite a bit tricky because of rank and tacit programming.

Answer 4

Using factoradic representation

In the factoradic representation of a permutation an element i takes values from 0 to N-i. So a random permutation is just rand(0,i) for every N-i.

In J:

? |.>:i.52
2 39 20 26 ... 2 0 1 0 0 0

where ? x is rand(0,x-1) and |.>:i.52 is 52 51 ... 1

Then, if a is the value of ith factoradic, we do the swap: swap(deck[i], deck[i+a]). The list of pairs to swap are:

(,. i.52) ,. (,. ((?|.>:i.52)+i.52))
0 33
1 20
2  3
...
49 50
50 50
51 51

The swap we'll be using works like this:

deck
24 51 14 18 ...
deck =: 0 1 swap deck
51 24 14 18 ...

It's not really "by reference" but there are no real functions in J.

We'll use deck's length (#deck) to avoid using a constant.

Complete program in J:

deck =: 52 ? 52                           NB. Initial random deck
swap =: 4 : 'deck =: (x { y) (|.x) } y'   NB. Given swap "function"
f =: 3 : 0                                NB. function that calls the swap for a pair
({.y) swap deck
}.y
)
f^:(#deck) (,.,.[:,.]+[:?[:|.>:) i.#deck

Answer 5

Python

import random
def rand(x, y):
 return random.randrange(x, y+1)

def swap(deck, x, y):
 deck[x] ^= deck[y]
 deck[y] ^= deck[x]
 deck[x] ^= deck[y]

def shuffle(deck):
 if len(deck)>1:
  deck[1:]=shuffle(deck[1:])
  if rand(0,len(deck)-1)>0:swap(deck, 0, rand(1, len(deck)-1))
 return deck

print shuffle(range(52))

Answer 6

C#

Here's my own answer based on the Fisher-Yates algorithm. Should give you a perfect shuffle if your random number generator is good enough.

English version:

1. Repeatedly swap the card at deck[0] with the one at deck[v], where v is the face value of the card at deck[0]. Repeat until v == 0. This will partially sort the deck, but that doesn't matter. You now know Card 0 is at the front of the deck, which means you can steal that space in the array and use it as a loop counter. This is the key "cheat" for the problem of local variables.
2. Starting at position 1 (the second card in the deck), swap the card at i with the one at rand(i, 51). Note that you need rand(i, 51), NOT rand(1, 51). That won't ensure that each card is randomized.
3. Set deck[0] back to 0. Now the whole deck is shuffled except for the first card, so swap deck[0] with deck[rand(0, 51)] and you're done.

C# version:

public static void shuffle(int[] deck)
{
    while (deck[0] > 0)
        swap(ref deck[0], ref deck[deck[0]]);

    for (deck[0] = 1; deck[0] < 52; deck[0]++)
        swap(ref deck[deck[0]], ref deck[rand(deck[0], 51)]);

    deck[0] = 0;
    swap(ref deck[0], ref deck[rand(0, 51)]);
}

Javascript version:

while (deck[0] > 0)
    swap(0, deck[0]);

for (deck[0] = 1; deck[0] < 52; deck[0]++)
    swap(deck[0], rand(deck[0], 52));

deck[0] = 0;
swap(0, rand(0, 52));

...where swap(a, b) swaps deck[a] with deck[b].

Answer 7

Ruby, one line

Is this considered cheating? It should be as random as it gets.

deck=(0..51).to_a # fill the deck
deck[0..51] = (0..51).map{deck.delete_at(rand deck.length)}

(Ruby's rand method only takes one argument and then generates a number n such that 0 <= number < argument.)

Additionally - similar to sogart's Perl solution, but as far as I know it doesn't suffer from the problem:

deck = deck.sort_by{rand}

Ruby's sort_by is different than sort - it first generates the list of values to sort the array by, and only then sorts it by them. It's faster when it's expensive to find out the property we're sorting by, somewhat slower in all other cases. It's also useful in code golf :P

Answer 8

JavaScript

NOTE: This solution is technically not correct because it uses a second parameter, i, in the call to shuffle, which counts as an external variable.

function shuffle(deck, i) {
    if (i <= 0)
        return;
    else {
        swap(deck[rand(0,i-1)], deck[i-1]);
        shuffle(deck, i - 1);
    }
}

Call with shuffle(deck,52)

A complete working example (had to modify swap slightly because there is no pass-by-reference of ints in JavaScript):

function rand(min, max) { return Math.floor(Math.random()*(max-min+1)+min); }
function swap(deck, i, j) {
    var t=deck[i];
    deck[i] = deck[j];
    deck[j] = t;
}

function shuffle(deck, i) {
    if (i <= 0)
        return;
    else {
        swap(deck, rand(0,i-1), i-1);
        shuffle(deck, i - 1);
    }
}

// create deck
var deck=[];
for(i=0;i<52;i++)deck[i]=i;
document.writeln(deck);
shuffle(deck,52);
document.writeln(deck);

Answer 9

C++

#include <cstdlib>
#include <ctime>
#include <iostream>

int deck[52];

void swap(int a, int b) {
    deck[a] ^= deck[b];
    deck[b] ^= deck[a];
    deck[a] ^= deck[b];
}

int r(int a, int b) {
    return a + (rand() % (b - a + 1));
}

void s(int *deck) {
    swap(1, r(2, 51));
    deck[0] *= 100;

    for(deck[0] += 2; (deck[0] % 100) < 51; deck[0]++) {
        swap(deck[0] % 100,
          r(0, 1) ? r(1, (deck[0] % 100) - 1) : r((deck[0] % 100) + 1, 51));
    }
    swap(51, r(1, 50)); 

    deck[0] = (deck[0] - 51) / 100;
    swap(r(1, 51), 0);
}

int main(int a, char** c)
{
    srand(time(0));

    for (int i = 0; i < 52; i++)
        deck[i] = i;

    s(deck);
    s(deck);

    for (int i = 0; i < 52; i++)
        std::cout << deck[i] << " ";
}

Avoids swapping elements with themselves, so has to call twice to be random.

Answer 10

D

shuffle(int[] d){
    while(d.length){
        if([rand(0,d.length-1)!=0)swap(d[0],d[rand(1,d.length-1)]);
        d=d[1..$];
    }
}

Answer 11

Another Perl solution, which actually produces uniformly distributed output:

sub shuffle_integers {
    map int, sort {$a-int $a <=> $b-int $b} map $_+rand, @_;
}

say join " ", shuffle_integers 1 .. 52;

This solution uses Perl's rand, which returns a random number x in the range 0 ≤ x < 1. It adds such a random number to each integer in the input, sorts the numbers according to their fractional parts, and finally strips those fractional parts away again.

(I believe the use of the special variables $_, $a and $b falls within the spirit of the challenge, since those are how perl passes the input to map and sort, and they're not used for any other purpose in the code. In any case, I believe they're actually aliases to the input values, not independent copies. This is not actually an in-place shuffle, though; both map and sort create copies of the input on the stack.)

Answer 12

Java

I am surprised nobody stated the obvious: (I'll assume swap(x,x) does nothing.

    static void shuffle(){
        swap(1,rand(0,1));
        swap(2,rand(0,2));
        swap(3,rand(0,3));
        swap(4,rand(0,4));
        swap(5,rand(0,5));
        swap(6,rand(0,6));
        swap(7,rand(0,7));
        swap(8,rand(0,8));
        swap(9,rand(0,9));
        swap(10,rand(0,10));
        swap(11,rand(0,11));
        swap(12,rand(0,12));
        swap(13,rand(0,13));
        swap(14,rand(0,14));
        swap(15,rand(0,15));
        swap(16,rand(0,16));
        swap(17,rand(0,17));
        swap(18,rand(0,18));
        swap(19,rand(0,19));
        swap(20,rand(0,20));
        swap(21,rand(0,21));
        swap(22,rand(0,22));
        swap(23,rand(0,23));
        swap(24,rand(0,24));
        swap(25,rand(0,25));
        swap(26,rand(0,26));
        swap(27,rand(0,27));
        swap(28,rand(0,28));
        swap(29,rand(0,29));
        swap(30,rand(0,30));
        swap(31,rand(0,31));
        swap(32,rand(0,32));
        swap(33,rand(0,33));
        swap(34,rand(0,34));
        swap(35,rand(0,35));
        swap(36,rand(0,36));
        swap(37,rand(0,37));
        swap(38,rand(0,38));
        swap(39,rand(0,39));
        swap(40,rand(0,40));
        swap(41,rand(0,41));
        swap(42,rand(0,42));
        swap(43,rand(0,43));
        swap(44,rand(0,44));
        swap(45,rand(0,45));
        swap(46,rand(0,46));
        swap(47,rand(0,47));
        swap(48,rand(0,48));
        swap(49,rand(0,49));
        swap(50,rand(0,50));
        swap(51,rand(0,51));
    }

OK, ok, it can be shorter:

package stackexchange;

import java.util.Arrays;

public class ShuffleDry1
{
    static int[] deck = new int[52];

    static void swap(int i, int j){
        if( deck[i]!=deck[j] ){
            deck[i] ^= deck[j];
            deck[j] ^= deck[i];
            deck[i] ^= deck[j];
        }
    }

    static int rand(int min, int max){
        return (int)Math.floor(Math.random()*(max-min+1))+min;
    }

    static void initialize(){
        for( int i=0 ; i<deck.length ; i++ ){
            deck[i] = i;
            swap(i,rand(0,i));
        }
    }

    static void shuffle(){
        while( deck[0]!=0 ) swap(0,deck[0]);
        for( deck[0]=52; deck[0]-->1 ; ) swap(deck[0],rand(deck[0],51));
        swap(0,rand(0,51));
    }

    public static void main(String[] args) {
        initialize();
        System.out.println("init: " + Arrays.toString(deck));
        shuffle();
        System.out.println("rand: " + Arrays.toString(deck));
    }

}

Answer 13

Burlesque

What you are actually asking for is a random permutation of a list of integers? r@ will give us all permutations, and we just select a random one.

blsq ) {1 2 3}r@sp
1 2 3
2 1 3
3 2 1
2 3 1
3 1 2
1 3 2
blsq ) {1 2 3}r@3!!BS
2 3 1

Since we need true randomness, something Burlesque isn't capable of doing because Burlesque has no I/O functionality you'd need to provide some source of randomness through STDIN.

That's probably something I'll fix in later version (i.e. generate a random seed at startup and push it to the secondary stack or something like that, but the Burlesque Interpreter itself has no I/O).

Answer 14

Javascript

I'm not sure if it's "cheating" but my solution uses the native local array of a function's arguments. I included my self-made functions of rand() swap() and filldeck(). Of interesting note, this should work with a deck of any size.

    var deck = [];

    function shuffle(){
        main(deck.length);
    }

    function main(){
        arguments[0] && swap( arguments[0]-=1, rand(0, deck.length-1) ), main(arguments[0]);
    }

        function rand(min, max){
            return Math.floor( Math.random()*(max-min+1) )+min;
        }

        function swap(x, y){
            var _x = deck[x], _y = deck[y];
            deck[x] = _y, deck[y] = _x;
        }


        function filldeck(dL){
            for(var i=0; i<dL; i++){
                var ran = rand(1,dL);
                while( deck.indexOf(ran) >= 0 ){
                    ran = rand(1,dL);
                }
                deck[i] = ran;
            }
        }

    filldeck(52);
    shuffle();

Answer 15

Tcl, 32 bytes

Abusing time function which serves to measure how much time is spent a script is running, but also can serve as a looping mechanism without declaring any variables.

time {lswap $D [rand] [rand]} 52

Try it online!

Answer 16

perl - this is not a proper shuffle as explained in comments!

my @deck = (0..51);
@deck = sort {rand() <=> rand()} @deck;
print join("\n",@deck);

I think I didn't use anything as a swap etc. was that needed as part of the problem?

Answer 17

JavaScript 4 lines

function shuffle() {
  while(deck[0]!=0)swap(deck[0],rand(1,51))
  while(deck[0]++!=104)swap(deck[0]%51+1,rand(1,51))
  deck[0]=0
  swap(0,rand(0,51))
}

Original answer that wasn't random enough. The swap wasn't guaranteed to touch each item in the deck.

// shuffle without locals
function shuffle() {
  deck.map(function(){swap(deck[rand(0,51)],deck[rand(0,51)])});
}