How to loop through all the combinations of e.g. 48 choose 5

Question

Possible Duplicate:
How to iteratively generate k elements subsets from a set of size n in java?

I want to build my own poker hand evaluator but am having trouble with a particular part.

If two players get dealt a two card hand, then there will be 48 cards left in the pack. In Texas Hold'em a further 5 possible community cards are then dealt (this is called the board). I want to enumerate / loop through all the 48 choose 5 possible combinations of boards and count the times Player A wins and the times Player B wins and when they tie.

I'm not sure how I can systematically loop through every 5 card combination. Does anyone have any ideas? The cards are represented as an array of class Card, but I could also represent them as a bitset if this makes it faster.

I'm doing this in Java.

Many thanks

Answer 1

(disclaimer: I've written a very fast poker hand evaluator)

I want to enumerate / loop through all the 48 choose 5 possible combinations of boards and count the times Player A wins and the times Player B wins and when they tie.

You do not want to evaluate C(48,5) (1 712 304) hands every time you have a matchup between two players preflop: most programs simply use a precomputed lookup table between all the possible matchups between two players preflop.

For example say you have "Ac Ad" vs "7c 6c", you simply go look in a lookup table that contains: 1 333 573, 371 831, 6900 (where 1 333 573 is the number of times "Ac Ad" wins, 371 831 is the number of times "7c 6c" wins and 6 900 is the number of ties (they sum to 1 712 304). To gain some room you can discard the 6 900, knowing that the number of ties shall always be C(48,5) - (wins 1 + wins 2).

(more on the lookup table at the end of this answer)

But to answer your question:

I'm not sure how I can systematically loop through every 5 card combination.

If you do really want to loop trough every combination, you have to know that poker hand evaluators are typically the kind of program that need to be very, very fast. These programs can typically evaluate hundreds of millions of hands per second (you read correctly: hundreds of millions).

When you need such high-performance "number crunching" you can forget about "design patterns" and "OO". What you want is raw speed.

For example the following will pass through the innermost loop C(48,5) times and it is quite fast:

    for ( int i = 0; i < n; i++ ) {
        for ( int j = i + 1; j < n; j++ ) {
            for ( int k = j + 1; k < n; k++ ) {
                for (int l = k + 1; l < n; l++) {
                    for (int m = l + 1; m < n; m++) {
                        ...
                    }
                }
            }
        }
    }

Once again for two players preflop it's probably a very bad idea: you're gonna be much faster by using a lookup table.

But for three players preflop (where it's impractical to use a preflop tables, there are too many matchups), you may want to loop like that, over C(46,5) hands, using the five nested loops (of course you need to use i,j,k,l,m to get the correct 5 cards out of the 46 cards that are left). Then, once you've got the 5 cards, you use a fast hand evaluator that gives you the best out of 7 (the 5 of the board + the two of each player).

Regarding the lookup table:

Most people use an approximated 169 vs 169 lookup table ("Ac Kd", "As Kh", "Ad Ks", etc. all become "AK offsuit" and the C(52,2) possible starting hands become grouped in 169 type of starting hands). The Wikipedia article explains how to get the 169 non-equivalent starting hands:

http://en.wikipedia.org/wiki/Texas_hold_%27em_starting_hands

They're non equivalent when you take one hand into account, but as soon as you do hand 1 vs hand 2 the "169 vs 169" is an approximation (a quite good one that said).

Of course you can get fancier. There are only C(52,2) (which gives 1326) real different Hold'em starting hands, which means it's very practical to build a perfect lookup table (no approximation at all) on modern computers (C(1326,2) ain't that big) if you really need perfect numbers. If you can live with approximation, go for the 169 vs 169 table (it would need C(169,2) or 14 196 entries).

Answer 2

1. Initialize an array (A) to the first 5 indices. (0,1,2,3,4)
2. Move the last possible index in A to the next position. A[k]++
3. Move the following indices to the following successive positions. (A[k+1] = A[k] + 1, ...). If some index would become too large, try with an earlier index in step 2.
4. Yield the elements at the current indices in A.
5. If possible, repeat from step 2.

Implemented as an iterator:

public class CombinationIterator<T>
        implements Iterable<List<T>>,
                   Iterator<List<T>> {
    private List<T> items;
    private int choose;
    private boolean started;
    private boolean finished;
    private int[] current;

    public CombinationIterator(List<T> items, int choose) {
        if (items == null || items.size() == 0) {
            throw new IllegalArgumentException("items");
        }
        if (choose <= 0 || choose > items.size()) {
            throw new IllegalArgumentException("choose");
        }
        this.items = items;
        this.choose = choose;
        this.finished = false;
    }

    public Iterator<List<T>> iterator() {
        return this;
    }

    public boolean hasNext() {
        return !finished;
    }

    public List<T> next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        if (current == null) {
            current = new int[choose];
            for (int i = 0; i < choose; i++) {
                current[i] = i;
            }
        }

        List<T> result = new ArrayList<T>(choose);
        for (int i = 0; i < choose; i++) {
            result.add(items.get(current[i]));
        }

        int n = items.size();
        finished = true;
        for (int i = choose - 1; i >= 0; i--) {
            if (current[i] < n - choose + i) {
                current[i]++;
                for (int j = i + 1; j < choose; j++) {
                    current[j] = current[i] - i + j;
                }
                finished = false;
                break;
            }
        }

        return result;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Equivalent in C#, using an Iterator method:

public IEnumerable<IList<T>> Combinations<T>(IEnumerable<T> items, int choose)
{
    if (items == null) throw new ArgumentNullException("items");

    var itemsList = items.ToList();
    int n = itemsList.Count;

    if (n < 1) throw new ArgumentException("Must contain at least one item.", "items");
    if (choose <= 0 || choose >= n) throw new ArgumentOutOfRangeException("choose");

    var indices = Enumerable.Range(0, choose).ToArray();

    bool moreWork = true;
    while (moreWork)
    {
        yield return indices.Select(i => itemsList[i]).ToList();

        moreWork = false;
        for (int i = choose - 1; i >= 0; i--)
        {
            if (indices[i] < n - choose + i)
            {
                indices[i]++;
                for (int j = i + 1; j < choose; j++)
                {
                    indices[j] = indices[i] - i + j;
                }
                moreWork = true;
                break;
            }
        }
    }
}