3

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.

Improve this question
9
  • Sorry, I should have said that we can't use the Colections framework. Commented Apr 25, 2014 at 11:48
  • 1
    To avoid duplicates, check deck.contains()before pushing; that should show if the card is already in the shuffled desk. Commented Apr 25, 2014 at 11:50
  • 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. Commented Apr 25, 2014 at 11:56
  • Possible duplicate stackoverflow.com/questions/3951547/… Commented Apr 25, 2014 at 11:56
  • +1 for effort and showing us code Commented Apr 25, 2014 at 12:00

4 Answers 4

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

+1 for a solution that doesn't use additional memory ;)
@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.
@user2424380 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.
@user2424380 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...
@user2424380 I have used the answer in the link you gave to explore all the possible outcomes for 1 2 3
|
1

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

Improve this answer

1 Comment

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.
1

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.

Improve this answer

4 Comments

Instead of shuffling the array or int[], why not just shuffle the Card[]?
@PeterLawrey Yes, if he doesn't want to keep a "sorted" array of Cards, your option is definitely the best.
@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.
@ZouZou Thanks, that makes sense. This seems to work though List<Card> tempCards = Arrays.asList(protoDeck);
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.