How would I write a method that rearranges cards in a deck

Question

I need to split a deck of cards into two packets: the top half and the bottom half. This new array of cards is suppose to go: first card from from the top packet, first card from bottom packet, second card from top packet, second card from bottom packet, etc. If there are an odd number of cards then the top packet should have one more than the bottom packet. The top of the deck is the front of the array.

How would I go about doing this?

Here is the method I created to generate the deck of cards (I think it works):

private Card[] cards;
int value, suit;
private final int DECK_SIZE = 52;

public Deck()
    {
        int index = 0;
        cards = new Card[DECK_SIZE];
        //0 = spades, 1 = hearts, 2 = clovers, 3 =diamonds
        int suits[] = {0, 1, 2, 3};
        //1 = Ace, 11=jack, 12=queen, 13=king
        int values[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
        for (int suit : suits)
            for (int value : values)
            {
                cards[index] = new Card(value, suit);
                index++;
            }
    }

Answer 1

Before you go about doing what you say, note that a perfect shuffle is not a good idea if you are looking to randomize the order of a deck:

A perfect faro shuffle, where the cards are perfectly alternated, is considered one of the most difficult sleights of card manipulation, because it requires the shuffler to cut the deck into two equal stacks and apply just the right pressure when pushing the half decks into each other. If one manages to perform eight perfect faro out-shuffles in a row, then the deck of 52 cards will be restored to its original order. If one can do perfect in-shuffles, then 26 shuffles will reverse the order of the deck and 26 more will restore it to its original order.

---

If you want a random shuffle, on the other hand, the way to go is a Fisher-Yates shuffle. From the wikipedia page:

To shuffle an array a of n elements (indexes 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

Note, however, that depending on your randomness criteria, the standard Java random number generator may not be sufficient: (also from the Wikipedia page:)

For example, the built-in pseudorandom number generator provided by many programming languages and/or libraries may often have only 32 bits of internal state, which means it can only produce 2³² different sequences of numbers. If such a generator is used to shuffle a deck of 52 playing cards, it can only ever produce a very small fraction of the 52! ≈ 2^225.6 possible permutations. It's impossible for a generator with less than 226 bits of internal state to produce all the possible permutations of a 52-card deck. It has been suggested[citation needed] that confidence that the shuffle is unbiased can only be attained with a generator with more than about 250 bits of state.

Mersenne Twister is a well-known random number generator that would be adequate.

---

edit: for a literal answer to your original question, here's how I would probably do it (including a test method):

import java.util.Arrays;

public class Shuffle {
    /* assumes input and output arrays are same length (N) */
    static public <T> void perfectShuffle(T[] input, T[] output, int N)
    {
        int itop = 0;
        int ibottom = N - (N/2);
        /* bottom has (N/2) elements; for odd N this is rounded down,
         * and the top part has 1 more element */
        int k = 0;
        while (ibottom < N)
        {
           output[k++] = input[itop++];
           output[k++] = input[ibottom++];
        } 
        // handle last element for N = odd
        if (k < N)
           output[k] = input[itop];
    }

    public static void main(String[] args) {
        int N = 19;
        String[] in = new String[N];
        String[] out = new String[N];
        for (int i = 0; i < N; ++i)
            in[i] = Integer.toString(i);
        perfectShuffle(in, out, N);
        System.out.println(Arrays.asList(out));
    }
}

output of main():

 [0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9]

finally, the reason why you shouldn't use this for shuffling cards:

 public static void main(String[] args) {
    int N = 52;
    String[] in = new String[N];
    String[] out = new String[N];
    for (int i = 0; i < N; ++i)
        in[i] = Integer.toString(i);

    for (int k = 0; k < 8; ++k)
    {
        perfectShuffle(in, out, N);
        System.out.println(Arrays.asList(out));

        String[] tmp = in;
        in = out;
        out = tmp;          
    }
}

output:

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

Answer 2

I was looking for something similar (shuffling a JSONArray) in this question: An efficient way to shuffle a JSON array in java?

I ended up making my own shuffle method implementing this algorithm. For your example, it would be something like:

public Card[] shuffle(Card[] cards) {
    // Implementing Fisher–Yates shuffle
       Random rnd = new Random();
       for (int i = cards.length() - 1; i >= 0; i--)
       {
          int j = rnd.nextInt(i + 1);
          // Simple swap
          Card card = cards[j];
          cards[j] = cards[i];
          cards[i] = card;
       }
       return cards;
}

Answer 3

If you're able to substitute a non-perfect shuffle, try Collections.shuffle(). Your code would look something like this:

List card_list = Arrays.asList(cards);
Collections.shuffle(card_list);

or as @Mark Peters points out, the more concise:

Collections.shuffle(Arrays.asList(cards));