# 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`

:

```
0000000
0000001
0000010
…
1111111
```

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.