c++ - How can I iterate through every possible combination of n playing cards

Question

How can I loop through all combinations of n playing cards in a standard deck of 52 cards?

Answer 1

You need all combinations of n items from a set of N items (in your case, N == 52, but I'll keep the answer generic).

Each combination can be represented as an array of item indexes, size_t item[n], such that:

• 0 <= item[i] < N
• item[i] < item[i+1], so that each combination is a unique subset.

Start with item[i] = i. Then to iterate to the next combination:

• If the final index can be incremented (i.e. item[n-1] < N-1), then do that.
• Otherwise, work backwards until you find an index that can be incremented, and still leave room for all the following indexes (i.e. item[n-i] < N-i). Increment that, then reset all the following indexes to the smallest possible values.
• If you can't find any index that you can increment (i.e. item[0] == N-n), then you're done.

In code, it might look something vaguely like this (untested):

void first_combination(size_t item[], size_t n)
{
    for (size_t i = 0; i < n; ++i) {
        item[i] = i;
    }
}

bool next_combination(size_t item[], size_t n, size_t N)
{
    for (size_t i = 1; i <= n; ++i) {
        if (item[n-i] < N-i) {
            ++item[n-i];
            for (size_t j = n-i+1; j < n; ++j) {
                item[j] = item[j-1] + 1;
            }
            return true;
        }
    }
    return false;
}

It might be nice to make it more generic, and to look more like std::next_permutation, but that's the general idea.