Generating k-combinations with recursion in JavaScript

Photo credit: IglooHome

It’s no secret I love games — for their pedagogical value just as much as for their entertainment value. There’s no better way to learn to code than writing a game. Even simple games have rules, hierarchies, states and conditions — the skills required to solve those problems are no different from the skills engineers use to solve real-world problems.

If I’m learning a new programming language, one of the first things I usually do is try to write a game, and that game is usually poker. Poker’s a source of endless joy and pleasure for me because it’s a diabolically addictive logic puzzle — cleverly disguised, of course, as a casino betting game. Today, let’s revisit the subject of a very old blog post I wrote about poker, and use it to explore two important, widely-discussed software engineering concepts: k-combinations and head/tail recursion.

Background: the K Foundation

In math and comp sci, a combination is an unordered selection of items from a collection. If order matters, it’s called a permutation; the two are closely related and the study of combinations/permutations together is called combinatorics. The field is huge and has so many critically important applications:

• Performance evaluation: generating permutations of routes on a communication system to compare performance
• Molecular biology: generating combinations/permutations of atoms, molecules, DNA, genes, or proteins
• Natural language processing: text-matching algorithms which generate combinations/permutations of parts of speech
• Operations research: job scheduling and resource allocation problems solved with combinatorics
• Data mining and forensics: why not generate combinations of SELECT ... WHERE ... commands to look for, say, lost data or hidden data or evidence of a crime?
• In a broad sense, any kind of pattern-matching in images, sound, measurements of the physical world like temperature, pressure, conductivity…

All card games are combinatorics games; the deck is our collection, and the hand size is our k. Five-card Jacks or better, the game Vegas video poker is based on, is a 52-combination-5 game; hold-em and other stud poker varieties are 52-combination-7 games.

Heads I win, tails you lose

A few popular languages have built-in methods like Ruby’s combination() and Python’s itertools, but JavaScript, sadly, has no native/low-level combinatorics functions. To broaden our knowledge and satisfy our appetite for punishment, let’s write our own JS combination() method using recursion. (Please keep in mind there are great many combinatorics algorithms, many of which are very different from, and likely much faster than, the recursive approach I’ll discuss… but a detailed comparison/discussion of all of them is a job for PhD candidates — not Medium bloggers.)

First, a quick recap of recursion from a previous blog post of mine: recursion solves a big problem (the recursive case) by repeatedly solving an identical but smaller problem (the base case). The base case looks the same as the recursive case — just on a smaller scale. Recursion only works when the program eventually reaches the base case; without reaching a base case, a recursive method will repeat indefinitely.

I won’t bother with a photo credit for this meme because it seems to have been floating around since the dawn of time

One important distinction I didn’t discuss exists between head recursion and tail recursion; the recursive call may come before base case processing (at the top or “head” of the function), or after the base case (at the bottom or “tail”). I’ve illustrated this with the two factorial() functions below, which do the same thing:

const headFactorial = n => {
  if ( n > 1 ) return n * headFactorial( n - 1 );
  else return 1;
}
const tailFactorial = n => {
  if ( n === 1 ) return 1;
  else return n * tailFactorial( n - 1 );
}

These two recursion styles seem trivial, but you’ll see below the choice makes all the difference in our approach to generating k-combinations.

With our powers combined…

If a set has n elements, the number of k-combinations from that set can be expressed as a binomial coefficient with factorials:

This is simple to write, but with our poker example (52-combo-5) it results in some headache-inducing math…

…so let’s clean it up with some factoring:

This makes a lot of sense when you think about it in a more concrete way by imagining you’re at a poker table drawing a hand. When drawing your first card, you have 52 to choose from, when drawing your second you have 51 possibilities, and so on. Think about it: doesn’t this really mean that every combination is just previous heads with remaining combinations tacked on at the tail?

Let’s put this hypothesis to the test with the method below. It uses tail recursion, but it also keeps track of the head and tail of the collection we’re generating combinations for as we’re recurring:

const combinations = ( collection, combinationLength ) => {
  let head, tail, result = [];
  if ( combinationLength > collection.length || combinationLength < 1 ) { return []; }
  if ( combinationLength === collection.length ) { return [ collection ]; }
  if ( combinationLength === 1 ) { return collection.map( element => [ element ] ); }
  for ( let i = 0; i < collection.length - combinationLength + 1; i++ ) {
    head = collection.slice( i, i + 1 );
    tail = combinations( collection.slice( i + 1 ), combinationLength - 1 );
    for ( let j = 0; j < tail.length; j++ ) { result.push( head.concat( tail[ j ] ) ); }
  }
  return result;
}

A line-by-line breakdown: first we define a head and tail to keep track of where we are so far, and then define three base cases:

• We then return an empty array [] if the combinationLength is larger than the size of the collection, or if the combinationLength is zero.
• If the combinationLength is equal to the collection size, there is only one possible combination, i.e., the whole collection — so we return the entire collection in an array.
• If the combinationLength === 1, our possible combinations are just individual elements — so we return the collection map()ped to its elements as individual arrays (combinations) of length 1.

Otherwise, we loop through the collection and start recurring!

• Our head will be an array of a single element: the one at the current index defined by i in the for() loop.
• Our tail will be the result of a recursive call with combinationLength decremented by one —remember, without decrementing we’ll recur forever and crash! We tack on each element in tail to the end of our head, and since each represents a new combination, we’ll push each time to result.
• Finally of course we return result when we’re done recurring.

This is all easier to visualize when it’s less abstract so let’s test it out in the console:

const deck = [
  'Two of Clubs',      'Two of Diamonds',   'Two of Hearts',
  'Two of Spades',     'Three of Clubs',    'Three of Diamonds',
  'Three of Hearts',   'Three of Spades',   'Four of Clubs',
  ...trust me they're all there
];
const possibleHands = combinations( deck, 5 );
console.log( possibleHands.length );
  -> 2598960
console.log( possibleHands.slice( 0, 5 ) );
  -> [
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Clubs' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Diamonds' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Hearts' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Three of Spades' ],
    [ 'Two of Clubs', 'Two of Diamonds', 'Two of Hearts', 'Two of Spades', 'Four of Clubs' ]
]

We can see this method generates the correct number of possible five-card hands from a 52-card deck: 2,598,960, the same as the result of ( 52 * 51 * 50 * 49 * 48 ) / ( 5 * 4 * 3 * 2 ) (check for yourself if you don’t trust me).

Let’s try generating combinations with a smaller collection and add some console.logs to see what’s going on as it’s happening:

const combinations = ( collection, combinationLength ) => {
  let head, tail, result = [];
  if ( combinationLength > collection.length || combinationLength < 1 ) { return []; }
  if ( combinationLength === collection.length ) { return [ collection ]; }
  if ( combinationLength === 1 ) { return collection.map( element => [ element ] ); }
  for ( let i = 0; i < collection.length - combinationLength + 1; i++ ) {
    head = collection.slice( i, i + 1 );
    console.log( "head: ", head );
    tail = combinations( collection.slice( i + 1 ), combinationLength - 1 );
    console.log( "tail: ", tail );
    for ( let j = 0; j < tail.length; j++ ) { result.push( head.concat( tail[ j ] ) ); }
  }
  return result;
}
const oneThroughFive = [ 1, 2, 3, 4, 5 ];

If you copy this into a Node console and run combinations( oneThroughFive, 3 ), for example, you’ll see a spill of logs that look a little bit like the following:

head:  [ 1 ]
head:  [ 2 ]
tail:  [ [ 3 ], [ 4 ], [ 5 ] ]
head:  [ 3 ]
tail:  [ [ 4 ], [ 5 ] ]
head:  [ 4 ]
tail:  [ [ 5 ] ]
tail:  [ [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ]
head:  [ 2 ]
head:  [ 3 ]
tail:  [ [ 4 ], [ 5 ] ]
head:  [ 4 ]
tail:  [ [ 5 ] ]
tail:  [ [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ]
head:  [ 3 ]
tail:  [ [ 4, 5 ] ]
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 2, 5 ], [ 1, 3, 4 ],
  [ 1, 3, 5 ], [ 1, 4, 5 ],
  [ 2, 3, 4 ], [ 2, 3, 5 ],
  [ 2, 4, 5 ], [ 3, 4, 5 ]
]

This shows something interesting very clearly: we never actually print any tails until we’ve finished recurring or reach one of our base cases! The head is always a single element from the collection, with possible combinations from the tail tacked on — ensuring combinations are never repeated. The illustration below shows visually how it all happens as we recur through chunks of the collection oneThroughFive with a combinationLength of 3:

Conclusion

None of the clever tracking we use to generate k-combinations would be possible with head recursion. There are examples of the opposite, too: many sorting algorithms would not be possible with tail recursion. And there are many more examples of recursion best suited for other types of problems: so-called circular or mutual recursion, where two or more methods call each other recursively, best known to CompSci students everywhere from the Towers of Hanoi puzzle.

Every time a computer science professor solves the Towers of Hanoi problem with recursion, a tech angel gets its wings (Photo credit: Wikimedia Commons)

Recursion also has drawbacks — the big one, which I’ve mentioned before, is its potential for exponential growth which can slow your code to a crawl. If you’ve been copying this code into Node, you’ll notice generating possible hands from a 52-card deck takes several seconds — not ideal for a fast-paced poker game.

All this lays bare the importance of careful planning and research when considering recursive solutions to the problems you face in your engineering career. Consider the speed you need and the scale of your app before trying a recursive solution — though often unwieldy and impractical, recursion can occasionally be a godsend!