Checking for an integer in array

Question

I have an exercise to do in college, part of which consists of creating a pack of cards which must then be shuffled. I have the cards in an array (not shuffled) and want to shuffle them and push them onto a home made Stack, from which I can pop the cards off to deal them.

My problem is that I want to check that the random number I generate (and which represents one of the cards in the array) is not already in the Stack. From reading on this forum I have come up with the code below which, it seems to me should work. On debugging though I notice duplicates.

As per my comment below we can't use the Collections framework (edit)

private Stack<Card> deck;//to hold cards
private Card[] protoDeck;//to hold cards before shuffling
private Random randomer;

private int cardsDealt;//how many cards used. Used for other methods
private static final int TOTALCARDS = 52;//sets limit of deck for all decks

public void shuffle(){//remove cards from deck and put back in random order
    randomer = new Random();
    int[] temp = new int[TOTALCARDS];//to keep track of random numbers
    int rand = 0;

    for (int i = 0; i < temp.length ; i++) {
        do {//keep creating randoms if 
            rand = randomer.nextInt(TOTALCARDS);
            deck.push(protoDeck[rand]);//puts the Card onto the Deck in a random position
            temp[i] = rand;
        } while (!(Arrays.asList(temp).contains(rand)));//check if the number already used  
    }
}

---

@PeterLawrey I have tweaked the code slightly as follows as I only need to shuffle full decks and it works a treat, I will pop cards off the Stack to deal

---

public void shuffle() {
    randomer = new Random();
    for(int i = 0; i < TOTALCARDS; i++) {
        // pick a random card from the rest of the deck
        int j = randomer.nextInt(protoDeck.length - i) + i;
        // swap cards
        Card tmp = protoDeck[i];
        protoDeck[i] = protoDeck[j];
        protoDeck[j] = tmp;
        deck.push(protoDeck[i]);
    }

}

Thanks to Peter and all the other contributors. M.

Answer 1

Starting with

private final Card[] deck;//to hold cards before shuffling
private final Random rand = new Random();

You can do

public void shuffle() {
    // no need the shuffle the last card.
    shuffle(deck.length - 1);
}

// will leave the first N card random without duplicates.
public void shuffle(int numberOfCards) {
    for(int i = 0; i < numberOfCards; i++) {
        // pick a random card from the rest of the deck
        int j = rand.nextInt(protoDeck.length - i) + i;
        // swap cards
        Card tmp = deck[i];
        deck[i] = deck[j];
        deck[j] = tmp;
    }
}

The cost is O(N) where N is the number of random cards.

---

Imagine you have a small Deck like

AS AC AD AH 2S 2C 2D 2H

and you need to pick a random first card, you select one from the deck and swap that card. Say nextInt() is 5 => 2C

2C | AC AD AH 2S AS 2D 2H

The desk is made up of cards randomly selected + not selected. You have no duplicates because the same cards get moved around. The next random card is say 2H which is swapped with AC

2C 2H | AD AH 2S AS 2D AC

Finally AD happens to be selected.

2C 2H AD | AH 2S AS 2D AC

This gives you three random cards and the rest. The same array can be use again as starting with a sorted or random deck doesn't make the result any more or less random.

---

In reply to the answer Why does this simple shuffle algorithm produce biased results? if there is 123, the possible outcomes are

123
 +- 123          - swap 1 and 1 (these are positions, not numbers)
 |   +- 123      - swap 2 and 2
 |   +- 132      - swap 2 and 3
 +- 213          - swap 1 and 2
 |   +- 213      - swap 2 and 2
 |   +- 231      - swap 2 and 3
 +- 321          - swap 1 and 3
     +- 321      - swap 2 and 2
     +- 312      - swap 2 and 3

As you can see there is only 6 possible outcomes, all equally likely.