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.

Karolinekaroly

Sorry, I should have said that we can't use the Colections framework. – Karolinekaroly

To avoid duplicates, check deck.contains()before pushing; that should show if the card is already in the shuffled desk. – Reduction

Without using Collections.shuffle, you can use the same code. You can optimise the code to pick N random cards, rather than shuffling the whole deck. – Claribel

Possible duplicate #3952047 – Hoarfrost

+1 for effort and showing us code – Degroot

@PeterLawrey The trouble is the Card[] protoDeck has to contain 4 * Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King for the four suits, the suits aren't important for this exercise but we must have 4 of each card. – Karolinekaroly

"we must have 4 of each card" see my answer. It will allow you to select 4 random and unique cards. – Claribel

Only barely on topic but interesting read about card shuffling algorithms: cigital.com/papers/download/developer_gambling.php – Hildegard

@Trengot I might even look at that after I have finished this ##### assignment. – Karolinekaroly

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.

Claribel

+1 for a solution that doesn't use additional memory ;) – Frigorific

@Peter Lawrey:Sorry, but I don't think this will work. int j = rand.nextInt(protoDeck.length - i) + i; this line can give you 1 for every run because the parameter for nextInt is just an upper limit so the numbers won't be unique. – Oosphere

@Oosphere The number doesn't need to be. Imagine you are selecting a random card from a deck without replacing it. If you select another card, it won't be a duplicate because you are not selecting from a card you have already selected. Imagine your just pick the first card each time and the nextInt() is zero every time. You will pick the 0, 1, 2, 3, 4, 5 ... card. It is still unique. – Claribel

@PeterLawrey Thanks, I will have a look at this, as a matter of interest why do you have shuffle() and shuffle(int numberOfCards)? The number of cards will always be 52, that's why I have TOTALCARDS set to 52 – Karolinekaroly

@Karolinekaroly When you deal some cards, you often deal N random cards at a time, not always all 52. – Claribel

@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]); } } – Karolinekaroly

@Karolinekaroly That should work. Don't forget to clear() the stack if you need to reshuffle e.g. on a black jack. – Claribel

@PeterLawrey: Sorry, my mistake, it works. Howewer I'm still not a big fan of this kind of shuffling, see here why: #859753 – Oosphere

@Oosphere As long as the bias is towards the Casino, I'm sure they won't mind. I have already told (and demonstrated) to my kids why they should NEVER play Blackjack for money... – Karolinekaroly

@Oosphere I don't use that approach. Note: I swap with an ever decreasing number of cards to choose from. – Claribel

@Oosphere I have used the answer in the link you gave to explore all the possible outcomes for 1 2 3 – Claribel

@PeterLawrey: you got me with that +i... I've checked the probabilty tree and you're right. +1 :) – Oosphere

@Oosphere generating random numbers with an ever smaller range is also a micro-optimisation. – Claribel

Answer 2

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

Chantalchantalle

It is a home made Stack so I was hoping not to have to create all the methods from scratch. Good point though, I'll have a look at making the contains() method in my home made one. – Karolinekaroly

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.

Frigorific

Instead of shuffling the array or int[], why not just shuffle the Card[]? – Claribel

@PeterLawrey Yes, if he doesn't want to keep a "sorted" array of Cards, your option is definitely the best. – Frigorific

@PeterLawrey so that the original Card[] protoDeck contains the 4 batches of 13 cards in random order? That would remove a step alright and I could just create a new deck each time I need to shuffle. As it is for Blackjack I only need to shuffle if all the cards have been exhausted or there is a Blackjack. I'll definitely try this and get back to you. – Karolinekaroly

@ZouZou Thanks, that makes sense. This seems to work though List<Card> tempCards = Arrays.asList(protoDeck); – Karolinekaroly

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.

Oosphere

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.

Degroot

If this method is planning to return true if the element is in the array you have to do return Arrays.binarySearch(array, key) >= 0;. As the doc states "index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array" – Frigorific

@ZouZou: Ah you are right, let me edit. I read the docs again – Degroot