Shuffle a deck without local variables [closed]

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:

C#:

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.

closed as off-topic by Wheat Wizard, Steadybox, FantaC, pajonk, RɪᴋᴇʀDec 27 '17 at 20:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Wheat Wizard, Steadybox, FantaC, pajonk, Rɪᴋᴇʀ
If this question can be reworded to fit the rules in the help center, please edit the question.

• Many languages model arrays as effectively infinite, thus allowing $deck 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 17 Answers 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){ //Sort 0 into element 0 swap(0,deck) } while(deck<51){ //Run 51 times while(deck[deck+1]!=deck+1){ //Sort element deck+1 into position deck+1 swap(deck[deck+1],deck+1) } swap(0,deck+1) //Swap element deck+1 into position 0, thus increasing the value of deck by 1 if(rand(0,deck-1)){ //Swap the element at position deck to a random position in the range 1 to deck swap(deck,rand(1,deck-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 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
• +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? – aaaaaaaaaaaa Mar 17 '11 at 19:22
• I doubt anyone but Haskell programmers will say that their code is pointless and be proud of it. – aaaaaaaaaaaa Mar 18 '11 at 1:12
• This ((.) .) . (. (++)) and this (((.) . (,)) .) are my favorite. Wow lambdabot. Just, wow. – Dan Burton Mar 19 '11 at 22:12
• @eBusiness "point free" is not at all the same as "pointless". – fredoverflow Mar 1 '14 at 1:46

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
• This works in APL too. The syntax is the same, so I won't bother adding a new answer ({52?⍵} is an anonymous function that takes 52 random items from its argument, which here would be a list of 52 integers) – Arc676 Nov 6 '17 at 10:21

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
• You may like the a, b = b, a trick. – Ray Aug 30 '14 at 16:47

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#

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 with the one at deck[v], where v is the face value of the card at deck. 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 back to 0. Now the whole deck is shuffled except for the first card, so swap deck with deck[rand(0, 51)] and you're done.

C# version:

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

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

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

Javascript version:

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

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

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

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

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
• @JustinMorgan yes, 52 times it deletes a random card from deck and adds it to the internal list of results that map is accumulating. Then when there's nothing left in deck the map result gets copied into deck. Basically there's a temporary, but it's a language feature rather than an explicit variable :) – hobbs Sep 5 '14 at 19:36
• deck.sort_by!{rand} is shorter. – Eric Duminil Jul 22 '17 at 14:21

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! – aaaaaaaaaaaa 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. – aaaaaaaaaaaa Mar 17 '11 at 21:05

C++

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

int deck;

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 *= 100;

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

deck = (deck - 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 - 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, but not in the way you have. – Justin Morgan Mar 19 '11 at 3:51

D

shuffle(int[] d){
while(d.length){
if([rand(0,d.length-1)!=0)swap(d,d[rand(1,d.length-1)]);
d=d[1..$]; } } 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.) 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; 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 ) swap(0,deck); for( deck=52; deck-->1 ; ) swap(deck,rand(deck,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)); } } 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). 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 && swap( arguments-=1, rand(0, deck.length-1) ), main(arguments); } 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 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!

• Am I correct that this only performs 52 random swaps? That's not enough for a true shuffle. I ran it a few times and counted an average of 8 cards still in their starting positions, and the probability of that with a true shuffle is about 9x10^-6. – Justin Morgan Jul 24 '17 at 16:24
• @JustinMorgan: Can you please explain me better the probability calculation? – sergiol Dec 2 '17 at 23:57

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 – aaaaaaaaaaaa 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/… – aaaaaaaaaaaa Mar 19 '11 at 23:26

JavaScript 4 lines

function shuffle() {
while(deck!=0)swap(deck,rand(1,51))
while(deck++!=104)swap(deck%51+1,rand(1,51))
deck=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)])});
}
• Doesn't produce a true random shuffle. Here's a visualizer test: jsfiddle.net/muk1bthm. I changed your shuffle code slightly to match my swap implementation, but here it is verbatim: jsfiddle.net/m7km4u6g – Justin Morgan Sep 5 '14 at 19:22
• To clarify, the above comment applies to the new version, which still isn't random. – Justin Morgan Nov 2 '15 at 16:04