Issue with "deck shuffling" program: getting unexpected zeroes in results Java

Question

My assignment is to create a card deck shuffling program, but I am having an issue with the algorithm I have made to shuffle it. The idea is to take a card at random from the deck (values[]) and place it into the new shuffled deck (shuffled[]). However my program is spitting out shuffles that have too many zeroes in it. The original array contains int values 0-51. The first zero also always stays in the first slot for some reason. Here's my code:

public static void selectionShuffle(int[] values) {
    int[] shuffled = new int[52];
    for (int k = 51; k > 0;) {
        int r = (int)(Math.random() * (double)51);
        if (values[r] != -1) {
            shuffled[k] = values[r];
            values[r] = -1;
            k--;
        }
    }
    for (int i = 0; i < values.length; i++) {
        values[i] = shuffled[i];
    }

}

Results of 8 consecutive random selection shuffles
1: 0 22 40 43 6 14 31 4 47 1 36 41 0 3 24 12 5 39 27 23 11 28 50 38 7 18 16 32 17 20 21 2 8 13 15 46 19 26 9 48 25 34 45 42 10 33 29 49 30 44 37 35
2: 0 17 34 2 26 12 4 13 38 27 20 29 40 28 47 0 48 9 6 43 46 33 23 1 19 3 49 41 7 39 30 8 25 32 10 24 0 16 45 36 14 37 42 11 44 15 50 21 31 18 22 5
3: 0 23 2 44 20 38 45 46 47 27 50 7 26 28 0 21 24 37 11 19 40 10 1 29 36 14 30 12 25 22 16 6 39 0 0 8 18 33 9 48 42 43 34 13 32 17 41 15 49 4 3 31
4: 0 32 49 0 13 41 25 46 18 2 28 23 7 40 0 47 0 29 45 22 21 27 8 30 1 19 4 26 37 14 44 20 15 39 50 12 10 11 36 34 42 0 24 6 3 17 33 16 48 38 9 43
5: 0 29 26 13 1 15 0 20 47 9 17 21 30 34 28 0 22 18 0 3 6 2 0 38 12 48 23 27 11 16 42 32 39 40 33 0 37 44 50 41 46 49 8 24 10 7 14 25 19 45 36 4
6: 0 7 32 26 36 33 28 27 15 39 47 30 45 23 0 0 42 50 17 40 22 48 0 20 37 14 21 49 10 19 9 18 2 16 0 3 8 24 41 1 0 38 13 0 29 44 12 46 11 25 34 6
7: 0 9 0 21 29 18 48 33 45 20 15 24 44 46 47 0 36 2 39 28 0 12 0 50 19 42 32 27 8 38 37 23 0 11 25 13 10 3 0 34 26 40 17 0 41 7 30 14 1 22 16 49
8: 0 46 41 20 8 38 9 36 40 3 14 26 33 44 10 47 24 27 29 16 28 32 0 18 39 48 0 34 12 0 30 17 0 23 15 22 13 0 25 7 45 0 37 11 21 42 50 19 2 0 0 1

Dont you want your loop to include zero. in `for (int k = 51; k >= 0;)` — Yetti99, Dec 01 '14 at 16:24
[have a look here](http://gamedev.stackexchange.com/a/26553) — jbutler483, Dec 01 '14 at 16:26

score 1 · Answer 1 · answered Dec 01 '14 at 16:26

I think the issue is in the below line of code. If you don't initialize all values of the array greater than or equal to 0, it will not change the value. Since the default int value is 0, that is what is coming across.

for (int k = 51; k > 0;) {

should be

for (int k = 51; k >= 0;) {

score 1 · Answer 2 · answered Dec 01 '14 at 16:26

Fill a deck with 52 cards
Parse the deck 51 times, grabbing the card at rand() * (numOfCardsRemainingInDeck)
Shift all cards from 'plucked' position to endOfArray one position 'to the left'.
After 51 iterations, the last card remaining is stuck into the last position of your result deck.

Sergey Kalinichenko · Accepted Answer · 2014-12-01T16:48:14.240

The problem is that your algorithm takes 51 cards out of 52, leaving shuffled[0] at 0. You can see that that is what's happening by looking at the results of the shuffles: position zero is always set to zero, while the remaining positions are set to random values.

One of the cards remains unshuffled from the first iteration; zero takes its place.

The next iteration can shuffle that zero, too, so now you have three zeros. The next iteration may add yet another zero, and so on.

To fix this issue, make sure that the loop goes all the way to zero, i.e.

for (int k = 51; k >= 0;) {
//                  ^

You also need to multiply random by 52, because otherwise you would never hit the last element of the array:

int r = (int)(Math.random() * (double)52);

You could also make a new random number generator, and call nextInt(52) on it.

Note that hitting that last element may take a while. An alternative solution would be to run the loop 51 times, and then put the last remaining value that has not been reset to -1 into position zero.

When I do that, the program compiles but refuses to shuffle, leading me to believe that the program is stuck in an infinite loop because the if statement doesn't evaluate to true. Why would this be? — LordValkyrie, Dec 01 '14 at 16:41
@LordValkyrie That's because you cannot reach the 52-nd element (see the edit). — Sergey Kalinichenko, Dec 01 '14 at 16:50
Great, it worked! Makes a lot more sense now! Thanks a bunch. — LordValkyrie, Dec 01 '14 at 17:02

score 0 · Answer 4 · edited May 23 '17 at 10:26

I would suggest using a List for this action, instead of an array.

If you use a list<cards>, then you could use Collections.shuffle

Randomly permute the specified list using the specified source of randomness. All permutations occur with equal likelihood assuming that the source of randomness is fair. This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.

This method runs in linear time. If the specified list does not implement the RandomAccess interface and is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential access" list in place.

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

More info/Source

public class Card {
  String name;   // for simplicity, just the card's name
  public Card(String name) {
    this.name = name;
  }
  public String getName() {return name;}
}

// ...

List<Card> deck = new ArrayList<Card>();
initDeck();  // adds like 52 new cards to the deck

Collections.shuffle(deck);   // shuffle the deck
Card drawn = deck.get(0);    // draw the first card
deck.remove(drawn);          // remove it from the deck

Found here

I have to do it in a way that doesn't use a built-in shuffling algorithm as part of the assignment, unfortunately. — LordValkyrie, Dec 01 '14 at 16:40

Issue with "deck shuffling" program: getting unexpected zeroes in results Java

4 Answers4