Shuffling a deck

Question

My objective is to swap every element of a string array with a random element.

for (int i = 0; i < array.length; i++) { // scanning the deck
    int abc = rm.nextInt(77); // random object range
    String temp = array[i]; // swapping cards at random places
    array[i] = array[abc];
    array[abc] = temp;
}

I checked the code, and it seems to work. There’s no visible pattern of increase or decrease in the elements of the resulting array, and no repetition either. Am I right? Are there any problems in this code?

Answer 1

There is a problem with the distribution of your shuffle. Instead of choosing a random index from anywhere in the array, choose an index from zero to i (inclusive). This should prevent the same card from being shuffled twice* and ensure a more even distribution (think of it as being analagous to taking cards out of a deck at random and stacking them on a new pile. Once they're on the new pile, they don't move around anymore). This is essentially the Fisher-Yates shuffle.

Shuffling an array of strings "a", "b", and "c" using your algorithm, I got the following results from 100,000 runs:

abc: 14974
acb: 18531
bac: 18755
bca: 18225
cab: 14694
cba: 14821

Using the algorithm I just described, I got these results:

abc: 16515
acb: 16758
bac: 16523
bca: 16706
cab: 16788
cba: 16710

_{* By "prevent the same card from being shuffled twice" I mean that each card can only be the "initiator" of one swap; they can still be "displaced" by another card initiating a swap.}

Answer 2

I see some problems with it:

1. You are reinventing the wheel. Use Collections.shuffle();

2. The code only shuffles an array of 77 elements. What would you do if the array had 2 elements? What would you do if the deck contains more than 77 elements?

3. Your array is a list of Strings. No much reuse. Could not be part of a library.

4. You could at least move the swap to its own method:

    /**
     * Swaps the two specified elements in the specified array.
     */
    private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
   

5. Using a fixed random (rm.nextInt(77)) is a valid choice if your array only contains 77 elements, but it is not optimal. Since the distribution should be homogeneous, using rand(length) would be less efficient than rand(current_size_unshuffled_elements), which translates to

   for (int i=size; i>1; i--)
     swap(list, i-1, rnd.nextInt(i));
   

As others have pointed out, all these points will bring your solution to the level of Knuth-Fisher-Yates shuffle algorithm, and there's a very interesting article from Jeff Atwood talking specifically about the naive approach and the comparison against KFY: http://blog.codinghorror.com/the-danger-of-naivete/

Answer 3

The others have already posted out most points, so I'll briefly recap my opinion on them and provide an easier example:

1. You are using some random object range in int abc = rm.nextInt(77), I suppose you wan to use rm.nextInt(array.length) such that it scales with your input.
2. Please try to use meaningful variable names. int abc and Random rm are utterly meaningless, for abc I do not know a replacement right now, for rm I suggest random.
3. Your code currently only works with Strings, consider making it generic and providing primitive overloads.

But it can be done way simpler, just use Collections.shuffle. I can see you thinking: "It doesn't work with arrays", well... it does! Watch this and read the explanation:

public void shuffleArray(final Object[] array) {
    Objects.requireNonNull(array, "array");
    Collections.shuffle(Arrays.asList(array));
}

Explanation:

1. Use final Object[] array, as the array may be of any type and you cannot use generics with arrays.
2. Check if the array is not null. The code would have thrown the exception either way if array == null, but I think it is better to throw them upfront.
3. Wrap the array in a Arrays.asList(array) to convert it to a List<Object>.
   1. It created a List<Object> that is backed by the Object[] array. You can set and get elements (and more), but you cannot add or remove elements, as that would modify the backing array in a way that is not allowed.
4. Now just call Collections.shuffle(...) on the List<Object>.

Answer 4

Your algorithm is guaranteed to have bias.

Your program can draw \$77^n\$ different equally likely random sequences, but there are \$n!\$ possible permutations of input.

You can think of a sequence of random numbers as a ball, permutations of input as holes, and program as the process of throwing balls into the holes. Fair shuffler should end up with the same number of balls in each hole.

But it's impossible to evenly distribute \$77^n\$ balls into \$n!\$ holes — simply because \$77^n\$ is not divisible by \$n!\$.

Answer 5

By a strange co-incidence, this was one of the questions on this year's Google Code Jam - to write some code that would distinguish between your algorithm and an unbiased shuffling algorithm.

You've mis-implemented the Fisher-Yates algorithm in a very common way, which has a known bias - elements of the array tend to end up further down the list than they started.

Here's some code that'll test the bias. It includes a version of your algorithm that's been modified to work with arbitrary sized int arrays, and a corrected version of that algorithm (basically just a standard Fisher-Yates algorithm).

import java.util.concurrent.ThreadLocalRandom;

public class Shuffler {
  public static final int TEST_ARRAY_SIZE = 1000;
  public static final int ITERATION_COUNT = 1000;

  // OP's algorithm, modified to use int arrays
  public static void badShuffle(int[] array) {
    for (int i = 0; i < array.length; i++) { // scanning the deck
      int j = ThreadLocalRandom.current().nextInt(array.length); // random object range
      int temp = array[i]; // swapping cards at random places
      array[i] = array[j];
      array[j] = temp;
    }
  }

  // Correct Fisher-Yates shuffle
  public static void goodShuffle(int[] array) {
    for (int i = 0; i < array.length; i++) { // scanning the deck
      int j = ThreadLocalRandom.current().nextInt(array.length - i); // random object range
      int temp = array[i]; // swapping cards at random places
      array[i] = array[i + j];
      array[i + j] = temp;
    }
  }

  public static int testShuffling(Algorithm algo) {
    // Initialise array
    int[] testArray = new int[TEST_ARRAY_SIZE];
    for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
      testArray[i] = i;
    }

    // Shuffle it
    algo.shuffle(testArray);

    // And test the shuffling
    int accumulator = 0;
    for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
      if (testArray[i] < i) accumulator += 1;
      else if (testArray[i] >i) accumulator -= 1;
    }

    return accumulator;
  }

  public static void main(String[] args) {
    int n = 0;
    for (int i = 0; i < ITERATION_COUNT; i++) {
      if (testShuffling(Shuffler::badShuffle) < 0) n += 1;
    }
    System.out.println("Bad algorithm has negative skew " + n * 100.0 / ITERATION_COUNT + "% of the time");

    n = 0;
    for (int i = 0; i < ITERATION_COUNT; i++) {
      if (testShuffling(Shuffler::goodShuffle) < 0) n += 1;
    }
    System.out.println("Good algorithm has negative skew " + n * 100.0 / ITERATION_COUNT + "% of the time");
  }

  public interface Algorithm {
    public void shuffle(int[] array);
  }
}

It shuffles a list of integers, and then counts how many of the integers have moved up the list, and how many have moved down, and produces a score which is the the difference between these two.

In a fair shuffle, you'd expect this score to be around zero, so it'd be positive roughly half the time, and negative roughly half the time. However, running the test with TEST_ARRAY_SIZE = 1000, you'll probably get something like:

Bad algorithm has negative skew 99.9% of the time
Good algorithm has negative skew 47.2% of the time

With TEST_ARRAY_SIZE = 78 (which I think is the size of deck you were using - presumably you're shuffling a tarot deck), things aren't much better:

Bad algorithm has negative skew 76.9% of the time
Good algorithm has negative skew 46.7% of the time

If you're determined to write your own code, I believe the algorithm in goodShuffle is correct. However, as others point out, you really are better off just using Collections::shuffle.