Random selection from 2D array without repetition

Question

I'm using CPP to make a blackjack game, but I'm stuck on how to randomly pick an element from my [4][13] array without repeating it and without shuffling the order of the array. Working in VisualStudio. So far I can only find answers for how to do this with a 1-D array. Anybody out there have suggestions?

Answer 1

A 2D array can easily be thought of a 1D array. You just need to do a little math.

If you have a solution that works for a 52 element 1D array (a new array with values 0-51 randomly ordered). do the following:

1. generate your random element, lets call it R (between 0 and 51).
2. now, convert that number into your 2D array system. (form of x,y)
   1. x = R / 13
   2. y = R % 13

Answer 2

Use std::random_shuffle to randomly shuffle a vector (say vector<int> v) from 0-51. Since random_shuffle shuffles the given vector, v is now your randomly shuffled vector.

v.back() returns the last element in the vector. So, the following code returns the last element (k) from your vector and then removes it. It also converts it to a double so you can compute k/13.

double k = static_cast<double>(v.back());
v.pop_back();

Now, since your matrix is 4x13, the kth element (row-major) is at row floor(k/13) and column k%13.

Answer 3

Well, one way to do this would be to add a bool field to the elements of the array, and when that element of the array gets picked set it to true. Then on future selections, check if that bool is true, and if it is, generate another random element. May not be the most efficient but it is simple.

With this, you could also easily create a method to iterate through the array and set all the bool fields to false to simulate a shuffle.

Answer 4

I would suggest you strongly consider using the std::deque<T> container. a double ended queue to represent the deck itself then you can push and pop 'cards' out of it as you deal them out.

Answer 5

A side note: don't hardcode the number 52: chances are you'd want to shuffle multiple decks in the same array. In the game of blackjack casinos often use multiple decks in blackjack "shoe", in particular 4 decks per shoe is quite common. This has significant implication on conditional probabilities: less correlation between the face up cards and face down ones. You won't want to shuffle the 52-card deck separately, you'd need to shuffle the entire N*52-card shoe. The algorithms proposed in the other answers would work with 3-D arrays as well as with 2-D arrays, with only minor modifications.

Answer 6

One method I always like was to take the 2d array and then generate 2 coordinates to swap. Do that n number of times and then you can just iterate through the 2D array using some for loops.

Answer 7

I would rather use a list with all the cards in it. IF you insist on a 2d array with [4] being suites [13] being numbers the answer is just as simple make the deck in place and never changing values however, make the array variables Boolean.

Ill write pseudo code.

initialize cardsselected to zero

Choose Card
        Randomly select 2 numbers 1 will be 0-3 and the other 0-12. 
        If the array at [random suite][random number] is not false 
             choose it 
             increment cardsselected 
             set value to false
             return true
        else if cardsselected  equals 52 return false
        else 
            run chooseCard() 
            return true

This is just a solution. It is not very optimized, it can take forever.

To optimize it.

You can keep Your 2d array to hold the cards in place just generating random numbers. To optimize the random number generation you can create a list of random numbers 1-52 and randomly pick from that. Then remove the number that was picked from the list.

Answer 8

There is a simple solution that involves using prime numbers. If you take a random initial index in your array (for simplicity, let it be a 1D array), then increment this index by a prime that is bigger than array length and take only the reminder after division by array length, you will obtain a sequence of random non-repeating indices.

Something like this:

#include <cstdlib>
#include <iostream>
#include <time.h>

const int Cols = 4;
const int Rows = 13;
const int N = Cols * Rows;

const int NPrimes = 12;
const int primes[NPrimes] = {59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107};

int prime = primes[0];
int index = 0;

void shuffle()
{
    srand(time(NULL)); // Random seed
    prime = primes[rand() % NPrimes]; // Get random prime number
    index = rand() % N; // Get random first index
}

// Compute next index in sequence
int nextIndex(int index)
{
    return (index + prime) % N;
}

int _tmain(int argc, _TCHAR* argv[])
{
    shuffle();

    for (int i = 0; i < N; i++) {
        int col = index / Rows;
        int row = index % Rows;
        std::cout << "[" << col << ", " << row << "] ";
        index = nextIndex(index);
    }
    std::cout << std::endl;
    return 0;
}

After N iterations the sequence will repeat itself, obviously.