0. set y = 1. set x = 0.

1. How many possible choices are there _given what we've picked so far_? Call it N.

2. Pick one of them. Call it 'a'.

3. set x = x + a * y. set y = y * N.

4. Repeat steps 1-3 until the number of choices drops to be less than 2.

Decoding is the same thing in reverse. Start with x. mod it with the first N. that's the first choice. divide by N, mod with the number of remaining choices. that's the second choice. etc.

For the case of n choose k, we get the rule that we can't pick anything lower than what has been picked so far. This means that first choice is one of (n-k+1) items. (We can't pick higher than that as we'd run out of choices before we reached k).

With this construction, we can see your case is easy. You just need to be able to signal that some choice was the last choice. So the each choice is from a set of N+1, being the N possibilities plus "picked nothing". Picking nothing means there's no remaining choices so it terminates.

Say we have n = 6 and k = 3 and we've already seen 4; what are possible choices at this point? If you allow 3 here it would be equivalent to picking 3 first then 4 and there would be a redundant encoding. You can "fix" this by fixing the order, so without a loss of generality let's assume a strictly increasing order. Then the worst case would be (1, 2, 3), where N is respectively 6, 5 and 4, resulting in log_2 120 = 6.90 bits of information entropy instead of the optimal log_2 24 = 4.32 bits.

The real fix would involve counting each subcases. There are 10 strictly increasing sequences starting with 1, 6 starting with 2, 3 starting with 3 and one starting with 4. The step 1 should account for this non-uniform distribution at the first place. The combinatorial number system described in the OP does this automatically.

The worst case of (1,2,3) is respectively 4, 3 and 2, resulting in log_2 24 = 4.32 bits.

The first choice isn't picking from 6, it's picking from 4. (because if 5 or 6 are chosen, then there's not enough following numbers to be able to choose 2 more numbers). That's the piece about '(n-k+1) choices for the first number'. 5 or 6 are not possible choices given the ordering requirement.

Oh, you are correct that the first number has only 4 possible choices. But what about the second number? It can't be 1 (already picked) and 6 (ordering requirement), but other numbers are open to pick. The third number is no different, it can't be 1 and 2 (already picked) but otherwise all other numbers are allowed. The resulting N would be 4, 4 and 4, i.e. 6 bits.

Maybe it helps to see the fuller picture:

  1st  2nd  3rd         2^(expected # of bits)
  
  1    2    3, 4, 5, 6  64
  1    3    4, 5, 6     48
  1    4    5, 6        32
  1    5    6           16
  
  2    3    4, 5, 6     36
  2    4    5, 6        24
  2    5    6           12
  
  3    4    5, 6        16
  3    5    6           8
  
  4    5    6           4

It's not quite as simple as just 2 bits per digit, because the last digit can only be large if the earlier digits are small.

This makes the worst case is (1,2,6) which encodes as 48, for 5.58 bits.

If you have a bijection between the items of some finite set S and {1,…,n} and a bijection between the items of some other finite set T disjunct with S and {1,…,m}, constructing a bijection between S ∪ T and {1,…,n+m} is trivial. For example, map the items of S to {1,n} as before and the items of T to {n+1,…n+m}, adding n to each of the values that you originally mapped each item of T to.

If you have a third finite set disjunct with S and T, it’s disjunct with S ∪ T, so you can repeat this construction.

“All subsets whose size is at most k” is the union of “all subsets whose size is zero”, “all subsets whose size is 1”, “all subsets whose size is 2”, … “ all subsets whose size is k”, and those sets are finite and disjunct, so you can use the above to construct such a mapping.

(as long as the set of common items is computable, “disjunct” is not essential in the above, but it would make the mapping more complex. “Finite” also isn’t necessary, as long as they’re countably infinite and you have finitely many sets. I think even a countably infinite number of countably infinite sets would work)

The solutions in the article certainly aren’t, with their for and while loops.

I think that’s moving the goalposts.

It depends on your cost model. If your cost model is with respect to n, this requirement does not move the goalposts because the solution in the article does not depend on n and k is fixed. Computing (1) the natural number corresponding to any n choose k subset or (2) the subset corresponding to any natural number n takes constant time (assuming a constant cost model for all naturals).

So, the result is in T. You subtract n, leaving 4, and use whatever bijection you had for T to decode that into an element of T.

If, on the other hand, you had n-4, you know it must decode to an element of S, and directly use its decoder to find that element.