📆 2024-02-16

N Choose K

Discrete Math for Indiscreet Games

I just published a small game Gauner Trio (roughly “Scoundrel Trio” in English), where the player must find the three culprits out of seven suspects. We often played the tabletop version of this game at home in my childhood, and I just wanted to implement it on my own in JavaScript.

Discrete Mathematics

The biggest issue is: How do you generate the cards showing all possible combinations of three suspects (out of seven)? Fortunately, PTSD kicked in and I remembered my university course on discrete mathematics. The operation is called n choose k and states that of all possible combinations of n items, pick the ones with k items. Wikipedia redirects you to the article Binomial coefficient, which is probably the term the professor used.

Being a programmer, I’m not very good at math, but I least can program. But how can the n choose k operation be implemented?

Bit Fiddling

Let’s consider a set of n bits, seven in our case. Each bit represents a suspect. If the bit is set to 1, the suspect is to be displayed on the card, and if the bit is set to 0, the suspect won’t be on the card.

To generate all the possible combinations of n bits, let’s just count from 0 up to the highest possible number that can be represented with n bits, e.g. 2 to the power of n, e.g. 2^7=128:

This gives us 128 unique combinations. However, the card stack is actually way smaller than 128 in the board game. This is because all cards show three suspects, and not 7 or 0. So we only need to consider the combinations with k bits set to 1 (and the other n-k bits set to 0).

So we need to

generate a sequence of numbers from 0 up to 2^n,
and filter all the numbers with k bits set to 1.

But how?

JavaScript Implementation

First, let’s iterate from 0 to 2^n:

const limit = Math.pow(2, n);
for (let i = 0; i < limit; i++) {
    // TODO
}

Now for each number, we need to figure out if it has k bits set to 1. We can apply the binary and operator to i to figure out if the rightmost bit is set to 1. Then the number i just needs to be shifted n-1 times to the right so that the other bits can be checked. Let’s do that for a single number i:

let mask = i;
let ones = 0;
for (let j = 0; j < n; j++) {
    if (mask & 1 == 1) {
        ones++;
    }
    mask >>= 1;
}

Notice that >>= is not a fancy functional operator, but the combination of the assignment = and the right shift >> operators.

Now if ones == k applies for i, then i represents a number with k bits set to 1. But how does this help us in the greater scheme of things?

Picking from Arrays

Let’s take a step back and look at what we’d like to achieve: We have n elements for which we’d like to create n choose k combinations of k elements. If those items are passed in as an array, we should return an array of length n choose k with k elements each:

const nChooseK = (elements, k) => {
    const choices = [];
    const limit = Math.pow(2, elements.length);
    for (let i = 0; i < limit; i++) {
        // TODO
    }
    return choices;
}

We’re not only interested in the number of 1 bits, but also in their exact positions, which translate to array indices for the elements to be picked. So here’s the code replacing the TODO comment above:

let mask = i;
const positions = [];
for (let j = 0; j < elements.length; j++) {
    if (mask & 1 == 1) {
        positions.push(j);
    }
    mask >>= 1;
}
if (positions.length == k) {
    const names = [];
    for (let position of positions) {
        names.push(elements[position]);
    }
    choices.push(names);
}

We actually no longer need to count the bits, but just add the bit index j to an array of positions. If we end up with a positions array of length k in the upper for loop, then all the names pointed to can be added as a new combination to the result set choices.

The n Choose k Function

Here’s the function in full:

const nChooseK = (elements, k) => {
    const choices = [];
    const limit = Math.pow(2, elements.length);
    for (let i = 0; i < limit; i++) {
        let mask = i;
        const positions = [];
        for (let j = 0; j < elements.length; j++) {
            if (mask & 1 == 1) {
                positions.push(j);
            }
            mask >>= 1;
        }
        if (positions.length == k) {
            const names = [];
            for (let position of positions) {
                names.push(elements[position]);
            }
            choices.push(names);
        }
    }
    return choices;
};

And here’s how it can be used (here with n=3 and k=2 for the sake of brevity):

nChooseK(["a", "b", "c"], 2); // [["a", "b"], ["a", "c"], ["b", "c"]]

With the original problem of n=7 and k=3, we get the following result:

let cards = nChooseK(["a", "b", "c", "d", "e", "f", "g"], 3);
cards.length; // 35

35 is not only what Wolfram Alpha answers to my query “7 choose 3”, but also the actual amount of cards in the original game. (Trust me, I double-checked in my mother’s attic.)

Exercises

There are various ways in which the code above can be improved. Here are some ideas:

Re-write nChooseK in TypeScript; i.e. add type annotations to make the intent of the parameters and variables more clear. Maybe a Set is the better choice than Array for this problem.
Re-write nChooseK in a functional style. The filter, map, and reduce methods of Array (or Set) might come in handy for this purpose.