Difference between shuffling algorithms

Question

Let's say we're to write a method to produce a shuffled deck of cards. Now to make it very simple, disregard the suits and so we have 52 cards.

One algorithm would be:

• Populate an array of 52 elements with 1 for first element, 2 for second, and so on.
• Write a for-loop that iterates X times, and during each iteration, pick two random cards and swap them.
• The bigger X is, the more randomized the shuffle will be.

Another algorithm:

• Populate an array like previously.
• Write a for-loop that iterates 26 times, and during each iteration pick two random numbers and put these two numbers at the successive front of another 52-element array that stores the newly picked numbers.
• In each iteration, remove the two cards from original array that are added to the new array.

I know there are better algorithms for shuffling but with regard to these two, which one is better and why?

Answer 1

The second algorithm appears to be an unrolled-by-two implementation of Fisher-Yates. This shuffle has the property of choosing one of all of the possible outcomes with a uniform distribution. What most would call a "fair" or "perfect" shuffle. There is no need to repeat the operation for extra randomness, provided your random number generator is providing unbiased results.

The first algorithm probably approaches I-don't-know-what-kind-of-distribution asymptotically. I would avoid it for a variety of reasons. Mostly because I don't know how large X needs to be before it produces a good shuffle, but I'm sure it's more than 52. I cannot think of a good application for this algorithm outside of deliberately simulating an inadequate shuffle.

The first algorithm is working in place, which is beneficial in some cases, but if you want that then you can modify the second algorithm to behave in a similar way.

Answer 2

You have to define what you mean by "better". The problem with the first algorithm is that it is possible that some elements never change place. For instance, if you never randomly get low numbers, the first cards will be in order.

The second algorithm will get you more randomization. If you only run it once, however, then items will be possible predictable in their final place.

I would either run algorithm 2 multiple times, or shuffle the cards like you do a real deck

1: Split the deck into two arrays of 26
2: Take the top card from one of the arrays at random and put it into a new array of size 52
3: Keep doing this until one array is empty, put the remaining cards of the other array into the size 52 array
4: Repeat

This will net you a nice randomization

Answer 3

The first algorithm produce highly biased distribution, as it's likely to leave some cards n their initial position and vulnerable to "dual-swap" problem (swapping the same two cards twice resulting in the initial cards state).

The second algorithm, as @sh1 mentioned is an unrolled version of Fisher-Yates algorithm, with one little exception: it's no more linear, as removing items from list is itself linear operation and it is executed at each iteration, thus overall algorithm complexity is O(n^2).

The efficient version of Fisher-Yates algorithm would be the following:

In pseudocode (since you haven't mention the language of choice)

for i from n − 1 downto 1 do
   j ← random integer with 0 ≤ j ≤ i
   exchange a[j] and a[i]

And python implementation, just in case :)

import random
n = 52
arr = [i for i in range(1,n+1)]

for i in range(n-1, 1, -1):
    elem_to_swap = random.randint(0, i)
    arr[elem_to_swap], arr[i] = arr[i], arr[elem_to_swap]

Answer 4

Better one is :

1. Generate 52 number in some temp array
2. Order the Array with cards using temp array as key

in C# it looks

Random r = new Random(DateTime.Now.Miliseconds);
string [] cards = new string[52]{"1","2",.....};
int [] temp = new int[52];
for(int i=0;i<52;i++)
{
    temp[i]=r.Next();
}

Array.Sort(temp,cards);