Java ArrayLists and randomized shuffling

[Sam Thompson]

Hi everyone:

As of right now I am currently working on a program that will create a deck of cards and then shuffle them in a variety of ways. However, I have been hitting a couple of snags. My code is presented below:

package Poker;

import java.util.*;
import java.lang.Math.*;

public class Deck_Shuffler
{
   String[] cardIndex = new String[52];
   String[] suites = {"Clubs", "Diamonds", "Hearts", "Spades"};
   int i = 0, j;
   
   ArrayList<String> deck = new ArrayList<String>(52);
   
   public Deck_Shuffler()
   {
       for (j = 0; j < cardIndex.length; j++)
       {
            if (j%13 == 0)
            {
                 cardIndex[j] = "ACE OF " + suites[i];
                 deck.add(j, cardIndex[j]);
            }
            else if (j%13 == 10)
            {
                 cardIndex[j] = "JACK OF " + suites[i];
                 deck.add(j, cardIndex[j]);
            }
            else if (j%13 == 11)
            {
                 cardIndex[j] = "QUEEN OF " + suites[i];
                 deck.add(j, cardIndex[j]);
            }
            else if (j%13 == 12)
            {
                 cardIndex[j] = "KING OF " + suites[i];
                 deck.add(j, cardIndex[j]);
            }
            else
            {
                cardIndex[j] = Integer.toString((j+1)%13) + " of " + suites[i];
                deck.add(j, cardIndex[j]);
            }
            if (j%13 == 12)
            {
                i++;
            }
       }
   }
   
   public ArrayList<String> randomGeneratedSHUFFLE()
   {
       Random mixItUp = new Random();
       int shuffledPosition;
       for (i = 0; i < deck.size(); i++)
       {
           shuffledPosition = mixItUp.nextInt(deck.size());
           try
           {
               if (!cardIndex[i].equals(deck.get(shuffledPosition)))
               {
                   deck.set(shuffledPosition, cardIndex[i]);
               }
               else
               {
                   throw new Shuffler_Exception("Space already occupied.");
               }
           }
           catch(Shuffler_Exception noOccupancy)
           {
               noOccupancy.spaceAlreadyOccupied();
               randomGeneratedSHUFFLE();
           }
       }
       
       return deck;
   }
   
   public ArrayList<String> interlaceSHUFFLE(int divide)
   {
       int upperQty = (int)Math.floor(cardIndex.length/divide);
       int lowerQty = cardIndex.length - upperQty;
       ArrayList<String> upperHalf = new ArrayList<String>(upperQty);
       ArrayList<String> lowerHalf = new ArrayList<String>(lowerQty);
       
       while (i < upperHalf.size())
       {
           upperHalf.add(i, cardIndex[i]);
           i++;
       }
       while (i < lowerHalf.size())
       {
           lowerHalf.add(i, cardIndex[i]);
           i++;
       }
       
       for (i = 0; i < cardIndex.length/2; i++) //first card in lower half of deck will be on top
       {
           deck.add(2*i, lowerHalf.get(i));
           deck.add(2*i+1, upperHalf.get(i));
       }
       
       return deck;
   }
   
   public class Shuffler_Exception extends Exception
   {
        public Shuffler_Exception(String message)
        {
            super(message);
        }

        public void spaceAlreadyOccupied()
        {
            System.out.println("This space already occupied.");
        }
        
        public void cardAlreadyShuffled()
        {
            System.out.println("This card has already been used.");
        }
   }
  
   public static void main(String[] args)
   {
       Deck_Shuffler shuffler = new Deck_Shuffler();
        //shuffler.createIndices();
        /*for (shuffler.i = 0; shuffler.i < shuffler.cardIndex.length; shuffler.i++)
        {
        System.out.println(shuffler.cardIndex[shuffler.i]);
        }*/
       ArrayList<String> shuffledDeck = shuffler.randomGeneratedSHUFFLE();
       for (int k = 0; k < shuffler.deck.size(); k++)
       {
           System.out.println(shuffler.deck.get(k));
       }
       System.out.println(shuffler.deck.size());
   }
}

The first problem I am having is with the first method: The RandomGeneratorSHUFFLE() method. I notice that it does seem to shuffle them but a few shuffled cards tend to REPEAT in the new simulated shuffled deck. Does anyone have any suggestions as to stop this from happening?

The second problem I am having is with ArrayLists in general. For example, in the interlaceSHUFFLE() method, I am having the computer "cut" the deck at a given point (either halfway, or at the 11th card from the top of the deck, or whatever) and then use this value to create two new mini-decks (ArrayLists). From there I want the program to interlace the two decks. I hope this is clear enough for you. I have a feeling it is more conceptual than specific that I am doing wrong. Anyone have any ideas?

For example, when I invoke the interlaceSHUFFLE() method, it is supposed to come up with the cards interlaced with one another. But it keeps giving me an error message, saying that there is nothing in the ArrayLists! How can this be? I've got to be doing something significantly wrong somewhere.

Any suggestions or advice would be greatly appreciated.

Thanks in advance everyone!

S.T.

[Steve Luke]

You store / reuse your indexing variables in your class. There is absolutely no reason you should do that. There are lots of reasons you shouldn't.

Reason 1 why you shouldn't Behavior changes depending on the order you call your methods. If you called the interlaceing method first, it would work, at least partly. But since you call the random generator one first, it can't work. Why? Because the random generator method increments i up through the size of the deck, then you reuse i in the interlaceing method, and you check to see if it is less then ~ half your deck. It won't be, because the other method incremented it to 52. You then reuse i as a counter again when you count through the second part of the deck in the interlaceing code. Since the first loop increments i up through ~ half your deck, then you run the second loop only when i is < ~ half your deck, it will not run as you would expect (it'll only run at all if the lower deck is larger than the upper deck, and then only by the difference in the card counts).

Your variables should be kept in the smallest possible scope. For loop counters, that means defining them in the loop when you can, which is why the for loop is so commonly written as:

for(int i = startPosition; i < desiredCount; i++)

Secondly, in the interlace method, you are using this condition: while (i < upperHalf.size()0. When this is run for the very first time, nothing has been added to the list. What do you think size() returns? Read the api before answering. Hint, size is not the method to be calling there. You don't even need to call a method here: you already know how many cards to add. Which value would tell you when to stop?

[Steve Luke]

For the random method, you start with a list that is completely full. Then, for each of the 52 cards (call it index), you generate a random number from 0 to 52 (call it position). You then take the card in the array at index and put it into the list at position, replacing the card already at that position. The only check you make is that the card at index is not the same card at position, which you define as being not allowable (the error says the space is already occupied, which makes no sense because all the spaces are already occupied. And it seems arbitrary that card #5 in the array can't randomly become card #5 in the list. Why is that not allowed?)

But remember that the random generator has no memory. It can repeat the numbers it generates. So, for example, it could generate the number 18 twice. You would then be placing two cards in the in slot 18 in the list. Since this process is performed exactly 52 times, if slot 18 in the deck is filled twice then one other slot in the deck was not replaced at all, leaving it at its original position. There is a good chance that the card already filling this spot in the deck had been placed into another slot in the deck at some point in the process. That would mean the card would end up both where it was set() and were it was to begin with. You shouldn't consider this to be a rare instance, it will be common. Your approach with the random generator does nothing to ensure each card is placed, and placed only once. Because of this it will nearly always produce bad results.

Also, your use of exceptions is very bad in my opinion. You check a condition, and when it is false, you throw an exception in the for loop. You immediately catch it in a surrounding try/catch. You then re-use the exception class to display specific methods. This is not very good design. Exceptions should be exceptional, they should not be used for flow control - and that is how you are using it. Since you use a conditional statement (if) one of the consequences of which is to cause an exception, whose purpose is to break out of the for loop - why do you use the exception, and why not just use break; It is much clearer (the main point) that you mean to exit out of the for leap in this condition, and probably more efficient.

for (...)
{
    if (someCondition)
    {
        ...
    } 
    else 
    {
        //condition false, show message, and break
        reportBadThingymagig();
        break;
    }
}

I guess you could say 'but I want to make sure I restart the shuffle again if the bad thing happens.' In that case, maybe a loop is in order:

boolean workDone = false;
while(!workDone)
{
    for (...)
    {
        if (...)
        {
            ...
            workDone = true;
        }
        else
        {
            reportBadThigyMagig();
            break;
        }
    }
}

I dunno, maybe there is a more elegant solution, but throwing an exception isn't one of them (in my opinion anyways...)

[Steve Luke]

I realize I got your exception handling wrong. It is even worse. You don't use the exception to break out of the for loop. You do the try/catch in the for loop which means it serves no purpose over the already present if/else code. Additionally, since the catch clause calls the random method again, you could cause the exception at card # 1, cause the deck to be re-shuffled as part of the exception handling, then have the deck be finished shuffling starting at card #2. Very inefficicient and a possible source of serious issues.

[Sam Thompson]

Steve:

Thanks for the input.

You brought up some interesting points I will try to address and try to improve on the code.

You said the code does nothing about making sure every card is placed and placed only once? How would I do that exactly? What suggestions/improvements? I KNOW what the process should look like. I've already drawn a few diagrams to help clarify it in my mind when it comes time put it into action in the code.

I will remove the exception part of the code.

Thanks.

S.T.

[Steve Luke]

When you randomly choose a card from a deck and put it into a new pile, you are sure to get each card once and only once. Why? Because you remove the card from the source pile as you put it in the result pile. That is the process you need to emulate.