# Shuffle a deck without local variables

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 (i.e. assumed to exist already):

• A length-52 array of integers representing the deck. When you start, deck contains exactly one of each card in some unknown order.
• A function, int rand(int min, int max), that returns a random integer between min and max, inclusive. You can assume that this function is truly random.
• A swap function that takes two ints (by reference) and runs the XOR swap algorithm. If you call swap(x, y), the values of x and y will be exchanged.

Result:

• deck should contain exactly one of each integer from 0 to 51 (inclusive), in a completely random order.

Difficulty:

• 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.

Clarifications:

• deck can be a global variable, or you can take it in as a parameter.
• Obviously you can change what's in deck (that's the point), but you can't change its size.
• Card values don't really matter, but let's say they're valued in S-H-C-D order, so 0 is the ace of spades, 12 is the king of spades, and 51 is the king of diamonds.
• Execution time doesn't matter, but true randomness does.
• You can write this in any language, but no fair using stuff like PHP's shuffle function.
• This isn't really code golf, but feel free to minimize/obfuscate your code. Even without removing whitespace, IIRC I can do it in something like 4 lines in C# or PHP.

I have a test program somewhere around here that plots the frequency of each card in each position. I'll post it when I get the chance, or you can write you own for a little extra credit.

Edit: Here's some test code to check for randomness in your results:

As a testing method it's not terribly strong, but it makes it easy to visualize severe problems in the shuffling. Ideally, the result should look like snow without any apparent pattern. Certain mistakes in the randomization will cause noticeable patterns in the result. It also throws an exception if you don't have exactly one of every card.

Here's an example of the visualizer's output comparing two shuffle methods, one truly random and the other one only partially so:

As you can see, patterns in the results should be easy to spot.

-
Many languages model arrays as effectively infinite, thus allowing \$deck[52] and onwards to be used in place of local variables. Perhaps this should be prohibited too. – Timwi Mar 17 '11 at 18:02
Are functions considered variable? are function parameters considered variables? – zzzzBov Mar 17 '11 at 18:37
@zzzzBov - What I had in mind was that function parameters would be considered variables, but I didn't specify that before @mellamokb's answer. I know it can be done without any parameters other than deck itself. – Justin Morgan Mar 17 '11 at 18:44
@eBusiness - That's a problem with me, not the question itself. And I was upvoting because the answerer found a loophole. – Justin Morgan Mar 17 '11 at 19:58
@user unknown - I think I understand. The answer is basically that you can assume whatever implementation of swap you like, as long as it fulfills its basic purpose. Part of my reason for making swap a given was so that people could treat it as 'magic' and concentrate on the main problem without having to worry about it working in their language of choice. You can either do that or write your own swap, it's up to you. – Justin Morgan Apr 20 '11 at 23:19

# 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>")
}
-
 That's exactly what I had in mind. Soon as I test this I'll upvote and probably accept. – Justin Morgan Mar 17 '11 at 23:52 Appears to work fine, although on closer inspection it's not exactly the same as mine. Accepted, and I'll post my own answer soon. – Justin Morgan Mar 18 '11 at 4:36 This is also known as Knuth shuffle algorithm (en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). – Bob Apr 19 '11 at 10:14

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 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
-
+1 for Haskell. Now I have to learn Haskell so I can read this. :P – Justin Morgan Mar 17 '11 at 18:45
How is the progress stored? – eBusiness Mar 17 '11 at 19:22
@Justin E. Morgan: My point-free answer doesn't exactly jump out as "readable" to me. The second and third code blocks should be readable, though. – Joey Adams Mar 17 '11 at 20:33
I doubt anyone but Haskell programmers will say that their code is pointless and be proud of it. – eBusiness Mar 18 '11 at 1:12
This ((.) .) . (. (++)) and this (((.) . (,)) .) are my favorite. Wow lambdabot. Just, wow. – Dan Mar 19 '11 at 22:12
show 1 more comment

# 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.

-
 +1: Working on code-golf when supposed to be working.. lol I am too :P – mellamokb Mar 17 '11 at 19:11 Can you explain what this does for the J-impaired? I recently heard it described as an explosion in an emoticon factory (codegolf.stackexchange.com/questions/1294/anagram-code-golf/…), which sounds about right. – Justin Morgan Mar 17 '11 at 23:50 @Justin: Explanation added. – Jesse Millikan Mar 18 '11 at 3:58

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
-

# C#

Great job, everyone. Here's my own answer in C# based on the Fisher-Yates algorithm (6 lines, for those keeping track).

The idea is to partially sort the deck until deck[0] == 0. Once you know the value at that position, you can freely use it as a counter as long as you set it back to zero when you're done.

Then, for each position i from 1 to 51, you swap deck[i] with deck[rand(i, 51)] (not rand(1, 51), that will throw off the randomness). Finally, set deck[0] back to zero and swap it with a random card. Should be a perfectly random shuffle.

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

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);
-
Well done. What I had in mind was considering parameters of shuffle as variables, but I didn't specify that so +1. Nice use of recursion, too. – Justin Morgan Mar 17 '11 at 18:48
-1, doesn't generate all permutations, this is obvious because element 51 will never occupy it's original place, and because you only call rand enough to generate 51! permutations out of the possible 52! – eBusiness Mar 17 '11 at 19:20
@eBusiness: In the original spec, the deck is arbitrarily ordered, not necessarily in the order 1-52. I just used that because it was the easiest. – mellamokb Mar 17 '11 at 20:25
@eBusiness: I modified to allow for the possibility of leaving the element in the same spot, by using deck[rand(0,i-1)] instead of deck[rand(0,i-2)]. Also swap all the way to i=0 instead of stopping at i=1. Does that help? – mellamokb Mar 17 '11 at 20:28
Yup, that should do it, except that you now break the XOR swap specification. – eBusiness Mar 17 '11 at 21:05

## 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))
-
 What does the [1:] mean? Does that recurse on a sub-array of deck? – Justin Morgan Mar 21 '11 at 15:23 Yes, [1:] means the subarray from index 1 to the end of the array. So it recursively shuffles everything but the first element, assigns (copies) it back to the same place in the original array, then randomly places the first element somewhere. – Keith Randall Mar 21 '11 at 20:20 Very clever. I think this is one of the prettiest solutions on here, and it uses the Fisher-Yates algorithm correctly. +1. This has been a nice way for me to see the beauty of languages I'm not familiar with. – Justin Morgan Mar 21 '11 at 20:28

## 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.

-
swap(deck[rand(1, 51)], (deck[0] - 51) / 100); How will swap know where to put the second value? You're also missing a ). – Justin Morgan Mar 17 '11 at 20:13
Oops, thanks. I started moving that part during a revision and must have got distracted before finishing it :P – Matthew Read Mar 17 '11 at 20:35
Downvote wasn't from me, BTW. I'll test when I can. – Justin Morgan Mar 17 '11 at 21:23
OK. I made it easier to test by providing a full program. – Matthew Read Mar 17 '11 at 21:44
Very clever. My own solution used deck[0], but not in the way you have. – Justin Morgan Mar 19 '11 at 3:51
show 1 more comment

# 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

-
 I wouldn't call it cheating, per se, but deck[0..51] does skirt the "no variables" rule somewhat by using a feature of the language. It's fair, I just think it loses some of the challenge. :) I don't know Ruby; can you explain the (0..51).map{deck.delete_at(rand deck.length)} part? Does that delete cards from deck? – Justin Morgan Apr 20 '11 at 20:27

## 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..\$];
}
}
-

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?

-
That would work if sorting by a random function was a way of producing an even random distribution. However it is not. -1 – eBusiness Mar 18 '11 at 2:10
and why is it not? could you give me a link to read??? – sogart Mar 19 '11 at 21:55
The quality of the result will vary greatly depending on the sort algorithm, but in almost all cases the result will be very far from an equal distribution random function. Here is an article on the subject: sroucheray.org/blog/2009/11/… – eBusiness Mar 19 '11 at 23:26
Thanks a lot, that was really informative! – sogart Mar 21 '11 at 16:05

## 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();
-
 It is cheating, I think. However, it's very clever cheating, so nice job. – Justin Morgan Dec 2 '11 at 19:02

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.)

-