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.

Answer 2

Actually Stack extends Vector. So you can use contains method to check that already element is there or not.

Answer 3

The original problem is that Arrays.asList(temp) does not create a List<Integer> but a List<int[]>.

Hence Arrays.asList(temp).contains(rand) returns always false.

If you used the wrapper class Integer (Integer[] temp = new Integer[TOTALCARDS];), it would work but your approach is very inefficient, as you will have to generate a "random" number in a set that would reduce at each iteration.

One way would be to create an array containing the position 0 to 51, shuffle it and then iterate through it to push the cards in the deck.

public void shuffle(){//remove cards from deck and put back in random order
    int[] temp = new int[TOTALCARDS];//to keep track of random numbers
    for(int i = 0; i < temp.length; i++){
        temp[i] = i;
    }

    //shuffle the array

    for (int i = 0; i < temp.length ; i++) {
        deck.push(protoDeck[temp[i]]);             
    }
}

This approach runs in O(n) time.

Answer 4

Maybe I got it wrong, but I think your concept is bad.

1. generate random number
2. put it in the new deck
3. check if it is already there

It sounds to me like a wrong order. On the other hand using a Set is always working if you want unique elements.

Answer 5

As @ZouZou states, Arrays.asList(temp) returns a List<int[]>. You may be doing this because of the confusion brought on by this answer (which wrong by the way). This answer shows a way you can do it using binary searching:

public boolean contains(final int[] array, final int key) 
{  
     Arrays.sort(array);  
     return Arrays.binarySearch(array, key) >= 0;  
}  

This modifies the passed-in array. You would have the option to copy the array and work on the original array i.e. int[] sorted = array.clone(); But this is just an example of short code. The runtime is O(NlogN).

Per the Java documentation, binarySearch will return one of the following (I highlighted the important points):

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.