Shuffling a deck?

Code:

---

#include <iostream>
#include <ctime>

#define LOW 2
#define HIGH 52

void Swap(unsigned int &A, unsigned int &B)
{
        int C = A;
        A = B;
        B = C;
}

class Deck {
        private:
                unsigned int Cards[52][2];
                time_t Seconds;
                unsigned int DeckSize;
        public:
                Deck();
                void Shuffle();
};

Deck::Deck()
{
        DeckSize = 52;
       
        time(&Seconds);
        srand((unsigned int) Seconds);
       
        unsigned int Values[13] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
        int i = 0, j = 0 , k = 1;
       
        for(i; i < 52; i++)
        {
                Cards[i][0] = Values[j];
               
                (j == 12) ? j = 0 : j++;
        }
       
        for(i = 0; i < 52; i++)
        {
                Cards[i][1] = k;
               
                (j == 12) ? (k++, j=0) : j++;
        }
}

void Deck::Shuffle()
{
        DeckSize = 52;
        int i = 52, RandomIndex = 0;
       
        for(i; i >= 2; i--)
        {
                RandomIndex = (rand() % (HIGH - LOW + 1) + LOW) % i;
                Swap(Cards[i][0], Cards[RandomIndex][0]);
                Swap(Cards[i][1], Cards[RandomIndex][1]);
        }
       
        for(i = 0; i < 52; i++)
        {
                std::cout << Cards[i][0] << " " << Cards[i][1] << std::endl;
        }
}

int main()
{
        Deck Foo;
        Foo.Shuffle();
        std::cin.get();
}

---

This is my code so far. The shuffle() function is not really supposed to print the deck but i did that for debugging purposes, so i could check how the deck got shuffled.

My deck is as you can see a 2 dimensional array of 52x2 unsigned integers. The first row is the Face Value of the card (Jack, Ace, 5 etc.), the second row is the suit of the card (Diamonds, Clubs and so on).

The algorithm i used loops through the deck from 52 to 2. It gets a random number (mod the loop index), and swaps the corresponding element in the array with the element of the index loop.

The output i get is almost what i wanted, the deck is shuffled, quite randomly. But one of the elements contains a huge number, instead of 2-14, and the suit element of that card contains 52 (or MAX). The number i get looks like an overflow error, but i've gone over the loops a million times, with no results.

1. Is my shuffling algorithm valid, or is there a better one i can use?

2. Where is the overflow error, i for sure as hell can't find it, and i'ts been bugging me for hours!

use the standard library.

Code:

---

class card
{
    enum Suite
    {
        Spades,
        Hearts,
        Clubs,
        Diamonds
    };
 
    enum Value
    {
          TWO,
          THREE,
          //etc...
          Jack,
          Queen,
          King,
          Ace
    };

    explicit Card(Suite s, Value v);
};

int main()
{
    std::vector<card> deck(52);
    deck.push_back(Card(Card::Spades, Card::Ace));
    deck.push_back(Card(Card::Hearts, Card::Queen));
    // add all the cards

  std::random_shuffle(deck.begin(), deck.end());
}

---

Quote:

---

Originally Posted by ChaosEngine

use the standard library.

Code:

---

class card
{
    enum Suite
    {
        Spades,
        Hearts,
        Clubs,
        Diamonds
    };
 
    enum Value
    {
          TWO,
          THREE,
          //etc...
          Jack,
          Queen,
          King,
          Ace
    };

    explicit Card(Suite s, Value v);
};

int main()
{
    std::vector<card> deck(52);
    deck.push_back(Card(Card::Spades, Card::Ace));
    deck.push_back(Card(Card::Hearts, Card::Queen));
    // add all the cards

  std::random_shuffle(deck.begin(), deck.end());
}

---

---

I'd rather write my own functions than using premade ones, even if they are more efficient and well-written, i'm only doing this because i want to learn, the day i wan't to make important software, i promise to use the std library for stuff like this ;)

Code:

---

int i = 52, RandomIndex = 0;
       
        for(i; i >= 2; i--)

---

Here your first index will be 52 - out of bounds.

Another thing: you probably don't need the defines. You already have a data member DeckSize which equals 52. And you seem to use LOW only in one place (but not in the for expression), so it's probably specific to this algorithm.

To improve the class:

Code:

---

class Deck {
        private:
        const static unsigned int Decksize = 52;
                unsigned int Cards[Decksize][2];
                //time_t Seconds; //has nothing to do with a deck
               
        public:
                Deck();
                void Shuffle();
};

---

* Use Decksize instead of HIGH.
** Card might be a class/struct of its own.

This looks like you're going too far:

Code:

---

void Deck::Shuffle()
{
        DeckSize = 52;
        int i = 52, RandomIndex = 0;

        for(i; i >= 2; i--)
        {
                RandomIndex = (rand() % (HIGH - LOW + 1) + LOW) % i;
                Swap(Cards[i][0], Cards[RandomIndex][0]);
                Swap(Cards[i][1], Cards[RandomIndex][1]);
        }

---

Try setting i to 0 to begin with.

[edit] Too late. [/edit]

Why do you have two arrays of size 52? You should have one array of size 52 since there are only 52 cards in the deck, and then use / or % to determine the face and suit. When you shuffle separately, you might end up getting two aces of clubs but no ace of diamonds.

Your shuffle looks ok if you can get your random index correct. It should be a random number in the range [0,i) (including 0, not including i).

I would not set i to 0 to begin with. Start it at 52 and work down to 1, making sure you get a random number in that range of [0,i). That way you'll stay in bounds.

You guys are right, i was too busy going through the loops too look at the index variables, i replaced the 52 with a 51 and it's working like a charm now, thanks a bunch :)

Quote:

---

Originally Posted by Daved

Why do you have two arrays of size 52? You should have one array of size 52 since there are only 52 cards in the decl, and then use / or % to determine the face and suit. When you shuffle separately, you might end up getting two aces of clubs but no ace of diamonds.

Your shuffle looks ok if you can get your random index correct. It should be a random number in the range [0,i) (including 0, not including i).

---

Nope, i will only get one of each suit, because when i shuffle, i swap both the Value and the Suit to the same position, i don't shuffle them seperatly.

>> working like a charm now
Are you sure your random numbers are distributed evenly? I'm not sure they will be.

Quote:

---

Originally Posted by Daved

>> working like a charm now
Are you sure your random numbers are distributed evenly? I'm not sure they will be.

---

Try and run the code then :)

Quote:

---

Your shuffle looks ok if you can get your random index correct. It should be a random number in the range [0,i) (including 0, not including i).

---

Actually that should be [0, i] - including i: it should be possible for a card to stay in the same place while shuffling.

>> Actually that should be [0, i] - including i
I guess either you start at 51 and include i or you start at 52 and swap with i-1.

>> Try and run the code then
Sorry, I don't have time, but you won't be able to tell by running the code once. You need to put the whole thing in a loop and run it hundreds or thousands of times keeping track of which numbers get in which spots and how many times. Then you can see if there are any issues. It is very common when implementing this yourself, especially when you don't follow the common formats, for the distribution to be slightly off. For example, maybe aces end up being dealt first 10% of the time and 8's only 5%.

Quote:

---

Originally Posted by Daved

>> Actually that should be [0, i] - including i
I guess either you start at 51 and include i or you start at 52 and swap with i-1.

>> Try and run the code then
Sorry, I don't have time, but you won't be able to tell by running the code once. You need to put the whole thing in a loop and run it hundreds or thousands of times keeping track of which numbers get in which spots and how many times. Then you can see if there are any issues. It is very common when implementing this yourself, especially when you don't follow the common formats, for the distribution to be slightly off. For example, maybe aces end up being dealt first 10% of the time and 8's only 5%.

---

I thought you meant that i would have an uneven number of cards in the different suits.

I have run the code around 200 times, and the second card in the array always seem to be either a 3, 4 or 5, not random at all. So i guess this must mean that i did something wrong within my shuffling algorithm right?

I can't observe this pattern.

I don't understand, though, why it must be so compliated to pick a number [0, i]

Why not

Code:

---

RandomIndex = rand() % (i + 1);

---

Daved may be referring to the fact that if (i + 1) in above statement is not a factor of RAND_MAX, the results tend to be biased but I don't think it would make that much difference here.

Once you are happy with what the code does, you might also consider cleaning it up style-wise.

* No need for the #defines.
* Once you have set DeckSize in the constructor, use it instead of magic 52 everywhere.
* Seconds makes no sense as a member of Deck class. In fact you don't need a separate time_t variable for srand() anyway.
* In for statements such as this:

Code:

---

    for (i; i < x; ++i)

---

the first expression (i;) does absolutely nothing (except producing a compiler warning if you have warnings enabled. Therefore you can just omit it:

Code:

---

    for (; i < x; ++i)

---

In C++, however, the loop counter is usually declared inside the for-expression:

Code:

---

    for (int i = qqq; i < x; ++i)

---

* Consider making Card a separate class / struct. (This will also help you get rid of the ugly 2D array and switch to random_shuffle more easily.)
* Consider using std::vector instead of the raw array.

Quote:

---

Originally Posted by anon

I can't observe this pattern.

I don't understand, though, why it must be so compliated to pick a number [0, i]

Why not

Code:

---

RandomIndex = rand() % (i + 1);

---

Daved may be referring to the fact that if (i + 1) in above statement is not a factor of RAND_MAX, the results tend to be biased but I don't think it would make that much difference here.

Once you are happy with what the code does, you might also consider cleaning it up style-wise.

* No need for the #defines.
* Once you have set DeckSize in the constructor, use it instead of magic 52 everywhere.
* Seconds makes no sense as a member of Deck class. In fact you don't need a separate time_t variable for srand() anyway.
* In for statements such as this:

Code:

---

    for (i; i < x; ++i)

---

the first expression (i;) does absolutely nothing (except producing a compiler warning if you have warnings enabled. Therefore you can just omit it:

Code:

---

    for (; i < x; ++i)

---

In C++, however, the loop counter is usually declared inside the for-expression:

Code:

---

    for (int i = qqq; i < x; ++i)

---

* Consider making Card a separate class / struct. (This will also help you get rid of the ugly 2D array and switch to random_shuffle more easily.)
* Consider using std::vector instead of the raw array.

---

I am going to use this code for a console based BlackJack game, and i am using the DeckSize variable to keep track of how many cards are left in the deck after i draw the top one, that is also why i didn't declare it as a constant.

About the time_t variable: The code i used is just something i basically copied from the FAQ on this site, i figured there would be nothing wrong with it then. I'll make sure i get rid of it though.

Thanks for the tips though, i will go through the game and alter my code once i got it done and it's working 100%, i'd rather not start rebuilding it before i've even finished writing it.

Quote:

---

Originally Posted by Neo1

Try and run the code then :)

---

Observing that the output of a program looks correct, is never proof of anything :-)

Quote:

---

I am going to use this code for a console based BlackJack game, and i am using the DeckSize variable to keep track of how many cards are left in the deck after i draw the top one, that is also why i didn't declare it as a constant.

---

OK then. But since you still need the magic 52 in many places, having a static const that represents the size of the whole deck wouldn't hurt.

Quote:

---

About the time_t variable: The code i used is just something i basically copied from the FAQ on this site, i figured there would be nothing wrong with it then. I'll make sure i get rid of it though.

---

I meant you can use it as a local variable where you need it. But don't make it a data member of the class. When you hold a real deck of cards in your hand, do you somehow feel that Seconds is a part of it?...

Quote:

---

Originally Posted by anon

OK then. But since you still need the magic 52 in many places, having a static const that represents the size of the whole deck wouldn't hurt.

---

Do you really think the size of a deck of cards is going to change? If it's standard Blackjack, how could it ever be played except with a standard deck?

I hardly think that 52 is a "magic" number in a program which plays a card game. Making it a macro or constant might imply that it could be changed to some other value.

But you can easily make a typo and have an array of size 5 that the compiler never catches. Its not a big deal but I would probably use the constant not the literal.

>> Daved may be referring to the fact that if (i + 1) in above statement is not a factor of RAND_MAX, the results tend to be biased but I don't think it would make that much difference here.
No, I wasn't referring to that. I agree that such an issue is not important for a toy application. I was referring to potential for something like the 3,4,5 thing mentioned, and basically saying what you said, the index calculation is way too complicated.

However, if you did want to make a real game that people play and make or bet real money with, then you would of course have to use a totally different and much more advanced random number generation scheme. There was an online poker site many years ago that tried to write a random shuffling algorithm like this that they thought was correct. Turns out it had tons of flaws and some guys were able to write a program that knew everybody's cards as they were playing.

Quote:

---

Originally Posted by brewbuck

Do you really think the size of a deck of cards is going to change? If it's standard Blackjack, how could it ever be played except with a standard deck?

I hardly think that 52 is a "magic" number in a program which plays a card game. Making it a macro or constant might imply that it could be changed to some other value.

---

You could be playing Casino style where they use up to 8 decks.

Quote:

---

Originally Posted by brewbuck

Do you really think the size of a deck of cards is going to change? If it's standard Blackjack, how could it ever be played except with a standard deck?

I hardly think that 52 is a "magic" number in a program which plays a card game. Making it a macro or constant might imply that it could be changed to some other value.

---

"Do you really think the amount of memory we'll need is ever going to be greater than 640KB...?"
One of the wonderful things about change, is that its so often unpredictable :)

by the way, have you never played a game which uses the Jokers? That would make your deck a size of 54..


Besides, even if it were a number which couldn't change (such as PI, or Gravity on planet earth) as others have mentioned, leaving literals lying around your code is undesirable.
.. Another good example is NULL, which is always 0, however, when defining a null pointer, which one would you use..?

>> Another good example is NULL, which is always 0, however, when defining a null pointer, which one would you use..?

0

http://www.research.att.com/~bs/bs_faq2.html#null

Just curious, when would you use (void*)0 or is that equivalent to 0? I did some googling but only found more confliciting discussions. Could someone explain the differences if any?

>> when would you use (void*)0 or is that equivalent to 0?
In C?