[mota7]

For the first case, you can't pick a number lower than any existing number. So if 4 is already picked, then only 5 or 6 can be picked, but if we pick 6, then there's no third number available to pick, so there only 1 possibility (picking 5). So it terminates.

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.

[lifthrasiir]

> 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.

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

Ideally (and necessarily) the last column should be 24 for all possible cases, but your algorithm can go anywhere from 4 (2 bits) to 64 (6 bits).

[mota7]

Nuts, you are correct that it isn't optimal.

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.