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());
}

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

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.

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

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

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.

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.