C++ Array Shuffle

Question

I'm fairly new to C++ and don't quite understand function parameters with pointers and references. I have an array of Cards that I want to shuffle using the Fisher-Yates shuffle. The deck is declared as

Card *deck[deckSize];

where deckSize has been declared as 24. The array is then initialized. I then call the shuffle function:

void shuffle (Card * deck[]) {
    int deckSize = 24;
    while (deckSize > 1) {
       long int k = lrand48();
       k = k %24;
       deckSize--;
       Card * temp = deck[deckSize];
       deck[deckSize] = deck[k];
       deck[k] = temp;
    }
}

If I try to print the value of a card after calling the shuffle function I get a seg fault. Any pointers on how to do this properly?

Answer 1

You declared deck as an array of pointers but you didn't allocate any space for it. If you de-reference it without allocating space you will get a seg-fault.

Answer 2

My C/C++ is rusty but I think your declaration:

Card *deck[deckSize];

is declaring an array of POINTERS to Cards. Don't you want this?

Card deck[deckSize];

and then declare shuffle:

void shuffle (Card deck[])

keep in mind arrays are 0-indexed. Not sure if you'd ever access the 24th element but that would be a boo-boo.

Answer 3

One immediate nitpick, you should always use the top-half of a random number because most implementations of random numbers have poorer randomness on the bottom half. So if long's are 32 bit you could use: k = (k >> 24) % 24 to get better randomness.

Second, the problem here is you are not setting temp. Your code should have a line: temp = deck[deckSize];.

Hope this helps.

Edit:

Further nitpick, your random number generator is also not big enough to sufficiently shuffle a deck of cards regardless of using the high bit or low bit. It only has 48bit long sequence, but to shuffle a deck you'd need at least a 226bit long sequence (52!, the number of ways to shuffle a deck, is a 226bit long number).

Answer 4

 Card *deck[deckSize];

I think you want:

Card *deck = new Card[deckSize];

Answer 5

It looks that your problem does not come from the code posted, which looks fine at a first glance, but from the code around it.

What about using a standard container of cards ? You must fill it, print it first to see if it's ok, shuffle, and then print it again.

#include <vector>
std::vector<Card> deck; // Empty for now. Must be filled with cards.


void shuffle (std::vector<Card> & deck)
{
    int deckSize = 24;
    while (deckSize > 1) 
    {
       long int k = lrand48();
       k = k %24;
       deckSize--;
       Card temp = deck[deckSize];
       deck[deckSize] = deck[k];
       deck[k] = temp;
    }
}

Answer 6

Basic arrays can't be defined with variable passed as size, as mentioned above.

And be careful there. Last element of

typename array[SIZE];

is array[SIZE-1], not array[SIZE]. It's probably where you getting a segfault.

You really should at lest try to use STL containers. STL has shuffle algorithms too (:

Answer 7

I think it might help to see the calling code.

class Card{
public:
    Card(int number):number_(number){}
    int getNumber(){return number_;}
 // ...
private:
    int number_;
};

void shuffle (Card * deck[]) {
    int deckSize = 24;
    while (deckSize > 1) {
       long int k = lrand48();
       k = k %24;
       deckSize--;
       Card * temp = deck[deckSize];
       deck[deckSize] = deck[k];
       deck[k] = temp;
    }
}

int main(int argc, char* argv[]){
{

  const int deckSize=24;
  Card* deck[deckSize];
  for(int i = 0 ; i getNumber()

That should work just fine.

Answer 8

People are complaining that you're not using containers and not declaring the size of your array. Don't worry about that, that's not the problem. Someone also said you're going past array boundaries, which you aren't. It's okay to have arrays with size not declared. It's also okay to have an array of pointers to Card. But the thing I don't get is why it crashes. Here's some sample code I wrote, based on your code:

#include <stdio.h>
#include <stdlib.h>
#define DECK_SIZE 24
void shuffle(int deck[]) {
    int n = DECK_SIZE, t;
    while (n > 1) {
        long k = lrand48() % DECK_SIZE;
        n--;
        t = deck[n];
        deck[n] = deck[k];
        deck[k] = t;
    }
}
int main(int argc, char **argv) {
    int deck[DECK_SIZE], i;
    for (i = 0; i < DECK_SIZE; ++i)
        deck[i] = i + 1;
    shuffle(deck);
    for (i = 0; i < DECK_SIZE; ++i)
        printf("%i\n", deck[i]);
    return 0;
}

Run it, it works perfectly fine. That means there is something else going on. Try printing the value of all the cards in your deck before you call shuffle to see if it segfaults there too, I suspect it would.

However, there IS an error in your code. Your function does not shuffle correctly. The correct way to shuffle is not to swap each card with a card selected from the entire deck, but to swap each card at position N with an card selected from the range 0..N. If you swapped each card with a random card you get N^N possible outcomes, some of which overlap if you swap a card back to its original place. With a 3 card deck it's apparent that this is wrong because you will end up with 27 different shuffles, some of which are the same, even though there are 3!=6 permutations of 3 cards. The problem is that since 6 is not a factor of 27, some permutations are more likely than others. To avoid this, try doing it this way:

void shuffle_correctly(int deck[]) {
    int i, t, k;
    for (i = 2; i < DECK_SIZE; ++i) {
        k = lrand48() % i;
        t = deck[i-1];
        deck[i-1] = deck[k];
        deck[k] = t;
    }
}

Answer 9

Just use std::random_shuffle found in <algorithm>, like this:

std::random_shuffle(deck, deck + deckSize);

and your deck with be shuffled.

Answer 10

You could also use

std::random_shuffle(deck, deck + deckSize)

which does Fisher-Yates for you.

However, there probably aren't enough bits in the standard random libraries to genuinely choose from all possible random permutations of cards.