Need C++ BlackJack Shuffle Example

[soulbee1]

Forgive my ignorance, I am learning. I am writing a C++ BlackJack program for school project. I have googled and incorporated the following code into my project. My results are I am getting a value for the cards of 2 - 5 and i do not understand why.
If someone can advise me of what I am doing wrong or have a good sample for me to look at would be greatly appreciated.

        int lowest=2; 
        int numCards=14;                    
// 2,3,4,5,6,7,8,9,10,J,Q,K,A
        int range=(numCards-lowest)+1;   
 // range of 1 to 14 card values
            srand(time(0));  // initialize seed "randomly"
            for(int i = 0; i < (120 - 1); i++)
            {
                    int randNum1 = (rand() % (range));
                    int randNum2 = (rand() % (range));
                    card *temp = myDeck[randNum1];
                    myDeck[randNum1] = myDeck[randNum2];
                    myDeck[randNum2] = temp;

            }

Thanks for your help in advance.

[VernonDozier]

Forgive my ignorance, I am learning. I am writing a C++ BlackJack program for school project. I have googled and incorporated the following code into my project. My results are I am getting a value for the cards of 2 - 5 and i do not understand why.
If someone can advise me of what I am doing wrong or have a good sample for me to look at would be greatly appreciated.
int lowest=2;
int numCards=14;
// 2,3,4,5,6,7,8,9,10,J,Q,K,A
int range=(numCards-lowest)+1;
// range of 1 to 14 card values
srand(time(0)); // initialize seed "randomly"
for(int i = 0; i < (120 - 1); i++)
{
int randNum1 = (rand() % (range));
int randNum2 = (rand() % (range));
card *temp = myDeck[randNum1];
myDeck[randNum1] = myDeck[randNum2];
myDeck[randNum2] = temp;

}
Thanks for your help in advance.

I think I'd have to see the rest of the code to be able to duplicate what you are getting exactly. Here are two code snippets I wrote that may be helpful:

http://www.daniweb.com/code/snippet1034.html
http://www.daniweb.com/code/snippet1019.html

One is easier to follow than the other.

My shuffling methods were different from what you are attempting. I'm not 100% sure what is going on with what you are doing (like I said, I'd have to see the rest of the code). Basically you are picking two random indexes and swapping the array elements of those two. That's a valid way of shuffling. I am wondering, though, if there is possibly some issue with your swap. Perhaps it is a shallow versus deep copy issue? Post more of your code so we can see the array initialization and the display function and can test it out.

Here's a way that worked and that looks like it is using the method you are trying to use, so the methodology is sound. Quite possibly the problem may also be somewhere in the code you haven't posted.

#include <iostream>
#include <ctime>
using namespace std;

int main ()
{
    srand (time (NULL));
    int cards[13];
    for (int i = 0; i < 13; i++)
        cards[i] = i;
        
    for (int i = 0; i < 200; i++)
    {
        int index1 = rand () % 13;
        int index2 = rand () % 13;
        if (index1 != index2)
        {
            int temp = cards[index1];
            cards[index1] = cards[index2];
            cards[index2] = temp;
        }
    }
    
    for (int i = 0; i < 13; i++)
        cout << cards[i] << endl;
        
    cin.get ();
    return 0;
}

[unbeatable0]

Why not use the built-in random shuffle() function from the header <algorithm> ?

[nucleon]

Here's a simple shuffle that ensures every element is moved at least once. Note the loop only needs 13 reps for 13 numbers.

const int MAX = 13;
int a[MAX];
for (int i = 0; i < MAX; ++i) a[i] = i;
for (int i = 0; i < MAX; ++i) {
    int r = rand() % MAX;
    int t = a[i]; a[i] = a[r]; a[r] = t;
}

[unbeatable0]

Here's a simple shuffle that ensures every element is moved at least once. Note the loop only needs 13 reps for 13 numbers.

const int MAX = 13;
int a[MAX];
for (int i = 0; i < MAX; ++i) a[i] = i;
for (int i = 0; i < MAX; ++i) {
    int r = rand() % MAX;
    int t = a[i]; a[i] = a[r]; a[r] = t;
}

You can't ensure that this code will move every element at least once because you can't ensure that r=rand()%MAX; won't give the exact value of i.
The code might also replace twice the same elements, causing no change.

[Clockowl]

const int MAX = 13;
int a[MAX];
for (int i = 0; i < MAX; ++i) a[i] = i;
for (int i = 0; i < MAX; ++i) {
    int r = rand() % MAX;
    while(r == i) r = rand() % MAX;
    int t = a[i]; a[i] = a[r]; a[r] = t;
}

That oughta take care of the first thing. ;D Shuffling the same elements twice is something that has in chance in real life as well, so it's part of being random. :)

[unbeatable0]

const int MAX = 13;
int a[MAX];
for (int i = 0; i < MAX; ++i) a[i] = i;
for (int i = 0; i < MAX; ++i) {
    int r = rand() % MAX;
    while(r == i) r = rand() % MAX;
    int t = a[i]; a[i] = a[r]; a[r] = t;
}

That oughta take care of the first thing. ;D Shuffling the same elements twice is something that has in chance in real life as well, so it's part of being random. :)

I didn't say it isn't random, I just said he can't ensure that every element moves at least once ;)

[Clockowl]

I didn't say it isn't random, I just said he can't ensure that every element moves at least once ;)

Well technically, they moved twice. But I catch your drift: it's not guaranteed that all the values will be at different indexes from where they started. Anyway, your first argument was pretty good, nobody would ever "switch" card 1 with card 1, so... I think that's a pretty good algo for randomizing stuff.

But, hey, we're C++, why not use STL's random_shuffle? Works on every STL container, suits the job just fine.

Here's a nice example: http://www.cplusplus.com/reference/algorithm/random_shuffle/

[nucleon]

You can't ensure that this code will move every element at least once

Good point. I don't know what I was thinking. An element should be allowed to stay in the same place, otherwise it is certainly not a random permutation.

[StuXYZ]

Sorry, but most of these solutions are inelegant and that is because to achieve randomness they require an excessive number of random number calls:

(a) Shuffling the stack by selecting two cards and exchanging requires about 7 times the deck of length to get to nearly random on a 52 deck set, and more on a later deck. It is because you can't ensure that you avoid leaving pairs (do this with a deck of 1,2,3,4 ... etc and shuffle and see how many consecuative pairs you have.

(b) If you loop through the deck index in the forward direction and then swap, you definately want the possibility that a card does not move. BUT this shuffle is flawed. Take a deck of 26 0 + 26 1 in that order ie. 0,0,0,0.....,0,1,1...1 and then shuffle. If you do the shuffle once and then add the first 5 cards you get about 2.55 and 2.45 for the sums as you repeat to an infinite number of tests. [i.e. shuffle the deck, sum, reset the deck] * infinity. That is a significant fraction for a casino to lose. The drift to pure randomness is asymptotic.

(c) Use the algorithm shuffle. Depends on implementation but normally very good

(d) something that is random is this: [ well significantly better than either (a) or (b) ]

int deckIndex[52];
int deck[52];
for(int i=0;i<52;i++)
   deckIndex[i]=i;

for(int i=52;i>=1;i--)
  {
     // ugly: Use a proper random number system e.g
     // Mesene Twister. 
     const int X=rand() % i;
      deck[i-1]=deckIndex[X];
      deckIndex[X]=deckIndex[i-1];
   }

Yes you have to use another array, but it is a temp, the calls to your random number generator are expensive. If you are doing many shuffles then you don't need to regenerate deckIndex as any list works. [you can cut one off the calls to the rng. but I haven't]

Note, I had look at random_shuffle under gcc/stl and it looks like a sophisticated version of (d) -- but I am not 100% certain of that.

[soulbee1]

Thank you for all of your suggestions! helped enormously!
keeping a note on the different shuffles ... will try them all when i have more time...
you guys are great!

[nucleon]

By jove, he's right! Below is a test program for the two shuffles.

StuXYZ: Your for loop condition should be i > 1, since when it equals one it always "switches" element zero with element zero.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define REPETITIONS 1000
#define ARRAY_SIZE    52
#define TEST_NUMS     10

typedef void (*shuf_func) (int[], int);

void shuffle1 ( int deck[], int size ) {
    int i;
    for (i = 0; i < size; ++i) {
        int r = rand() % size;
        int t = deck[i]; deck[i] = deck[r]; deck[r] = t;
    }
}

void shuffle2 ( int deck[], int size ) {
    int i;
    for (i = size - 1; i > 0; --i) {
        int r = rand() % (i + 1);
        int t = deck[i]; deck[i] = deck[r]; deck[r] = t;
    }
}

void init ( int deck[], int size ) {
    int i;
    for (i = 0; i < size / 2; ++i)     deck[i] = 0;
    for (i = size / 2; i < size; ++i)  deck[i] = 1;
}

int test ( int deck[], int size ) {
    int i, n = 0;
    for (i = 0; i < size; ++i) n += deck[i];
    return n;
}

void testShuffle (shuf_func shuffle) {
    int i, total = 0;
    int deck[ARRAY_SIZE];
    for (i = 0; i < REPETITIONS; ++i) {
        init ( deck, ARRAY_SIZE );
        shuffle ( deck, ARRAY_SIZE );
        total += test ( deck, TEST_NUMS );
    }
    printf ( "%f\n", (double)total / (REPETITIONS * TEST_NUMS));
}

int main() {
    srand ( time ( 0 ));

    testShuffle ( shuffle1 );
    testShuffle ( shuffle2 );
}

[StuXYZ]

No the loop condition is correct.
Let us investigate:
Consider my original code with the following, slight changes

int deckIndex[52];
int deck[52];
// ADD THIS BIT:
for(int i=0;i<52;i++)
   deck[i]=100;
// AS before
for(int i=0;i<52;i++)
   deckIndex[i]=i;

// as you suggest
for(int i=52;i>1;i--)
  {
      const int X=rand() % i;
      deck[i-1]=deckIndex[X];
      deckIndex[X]=deckIndex[i-1];
   }

// Add this:
std::cout<<"deck[0] == "<<deck[0]<<std::endl;

Now as you see deck[0] is unfortunately 100, that is definately incorrect. Hence I feel that you much have i>= 1 (or i>0) but not i>1.

However, you can write this:

for(int i=52;i>1;i--)
  {
     const int X=rand() % i;
      deck[i-1]=deckIndex[X];
      deckIndex[X]=deckIndex[i-1];
   }
deck[0]=deckIndex[0];

which is much better than the code I gave.

p.s. In my previous post the numbers 2.55 was for the sum of the first 5 cards in the deck and the sum 2.45 was for the last 5 cards. The text was not clear. There is a bigger difference to the expected mean of 0.5*N , where N is the number extracted from the deck as N tends to 1. I can see how to write the solution to the general case (I think) but haven't put the effort in to do so.

[nucleon]

I completely misread your algorithm. I didn't even realize it was using two arrays. That's an interesting trick. But your revised code is slightly better, so some good came out of it!

I'm getting some truly horrible numbers (for average sum of elements 0 to 4, i.e., the "front" of the array) from shuffleBad in this revised code:

/* Example run:
ShuffleBad:
  Front: 2.162890
  Back:  2.518120
ShuffleGood:
  Front: 2.501900
  Back:  2.500930
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define REPETITIONS  100000
#define ARRAY_SIZE   52
#define TEST_NUMS    5

typedef void (* shuffle_func ) (int[], int);

/* Always picks rnd int from 0 to size - 1 (inclusive) */
void shuffleBad (int deck[], int size) {
    int i;
    for (i = 0; i < size; ++i) {
        int r = rand() % size;
        int t = deck[i]; deck[i] = deck[r]; deck[r] = t;
    }
}

/* Picks rnd int from decreasing range */
void shuffleGood (int deck[], int size) {
    int i;
    for (i = size - 1; i > 0; --i) {
        int r = rand() % (i + 1);
        int t = deck[i]; deck[i] = deck[r]; deck[r] = t;
    }
}

/* Load first half of deck with 0, second half with 1. */
void initDeck (int deck[], int size) {
    int i;
    for (i = 0; i < size / 2; ++i)     deck[i] = 0;
    for (i = size / 2; i < size; ++i)  deck[i] = 1;
}

int sumFirstN (int deck[], int n) {
    int i, tot = 0;
    for (i = 0; i < n; ++i) tot += deck[i];
    return tot;
}

int sumLastN (int deck[], int size, int n) {
    int i, tot = 0;
    for (i = size - 1; i >= size - n ; --i) tot += deck[i];
    return tot;
}

void testShuffle (shuffle_func shuffle) {
    int i, totalFront = 0, totalBack = 0;
    int deck[ARRAY_SIZE];
    for (i = 0; i < REPETITIONS; ++i) {
        initDeck (deck, ARRAY_SIZE);
        shuffle (deck, ARRAY_SIZE);
        totalFront += sumFirstN (deck, TEST_NUMS);
        totalBack  += sumLastN (deck, ARRAY_SIZE, TEST_NUMS);
    }
    printf ("  Front: %f\n", (double) totalFront / REPETITIONS);
    printf ("  Back:  %f\n", (double) totalBack /  REPETITIONS);
}

int main() {
    srand (time (0));
    printf ("ShuffleBad:\n");   testShuffle (shuffleBad);
    printf ("ShuffleGood:\n");  testShuffle (shuffleGood);
}