I started developing some utilities related to Poker. Practically I wrote code in Java to help me compute all kinds of things related to the game of poker.

For example you hold two cards, you know the flop and you want to see how you stand against an opponent. In order to do this you must list all the other possible hands and all the combinations of 2 cards that represents the turn and the river cards. You compare all the possible hands and see in what percent of the cases you win and in what percent you lose and you know what are your chances. This is only an example but in order to achieve this you must write code to generate all combinations.

When I have to generate all possible solutions, the first (and only) algorithm that comes to mind is Backtracking. Recursive backtracking is really easy to implement so I’ve implemented one and it worked OK for combinations of 2 but for 3 i got heap overflow exceptions. The solution now is to implement an iterative backtracking algorithm. I could’ve modified the recursive one and transform it into an “ugly” iterative version but I said to myself that first I should check out some books or papers about backtracking. If I need it and I’m not remembering it so well, at least I got to try to understand it right this time.

So I opened Knuth – The art of computer programming – Volume 4A and I started with generating n-tuples and on the second page it struck me. In several lines of pseudocode it was this simple algorithm to generate all n-tuples, that you can use to generate all permutations and with some modifications you can also use it to generate all combinations. And above all it is not backtracking.

The idea is super simple. You start with a number expressed in n digits and you always add one to it and print the solutions. So you start with 00 and you add 1 and the number becomes 01 and you print the solution. Then you add 1 and the number becomes 02 and so on. When the number is 09 and you add one to it, it will become 10 and so on until 99.

When you want to generate combinations you must impose the condition that the digits are always in ascending or descending order. Also if you have more than 10 symbols to combine, you just use a different radix for each digit: in my case radix 52 because in a pack of cards you have 52 different cards. And if for each digit you have a different set of symbols you can use an array with different radices for each digit.

So simple and elegant!

Edit: An implementation of the idea above can be found at CardListGenerator.java from the jpokerlib project.