Solution to Oscar's challenge to come up with a way of encoding bit sets by assigning numbers such that bit sets with fewer on bits get lower numbers and the numbers can be mapped back to the bit sets. This is useful if the resulting numbers are then encoded in some sort of variable length encoding, and bit sets with small numbers of on bits are…

bits.py

#!/usr/bin/env python3

def population(bits, start=0):
    return sum(bits[i] for i in range(start, len(bits)))

def product(iterable):
    import functools, operator
    return functools.reduce(operator.mul, iterable, 1)

def n_choose_k(n, k):
    return product(range(1 + max(k, n - k), n + 1)) // product(range(2, 1 + min(k, n - k)))

def population_base(size, pop):
    "The number of bit patterns containing fewer than pop 1's out of n total bits."
    return sum(n_choose_k(size, k) for k in range(pop))

def number_to_population(n, size):
    "The population of the bitset with the given number."
    i     = 0
    total = 0
    while total <= n:
        total += n_choose_k(size, i)
        i     += 1
    return i - 1

def bits_to_number(bits):
    pop  = population(bits)
    size = len(bits)
    n    = population_base(size, pop)
    idx  = 0
    while pop > 0:
        size -= 1
        if bits[idx] == 0:
            n += n_choose_k(size, pop - 1)
        else:
            pop -= 1
        idx += 1
    return n

def number_to_bits(n, size):
    pop    = number_to_population(n, size)
    n     -= population_base(size, pop)
    idx    = 0
    bits   = [0] * size
    while pop > 0:
        size -= 1
        base = n_choose_k(size, pop - 1)
        if n >= base:
            n -= base
        else:
            bits[idx] = 1
            pop -= 1
        idx += 1
    return bits

if __name__ == '__main__':

    def generate_bits(size):
        "Generate all lists of bits of a given size."
        if size == 0:
            yield []
        else:
            for tail in generate_bits(size - 1):
                yield [0] + tail
                yield [1] + tail

    from sys import argv

    size  = int(argv[1]) if len(argv) > 1 else 5
    table = [None] * (2 ** size)

    for bits in generate_bits(size):
        n            = bits_to_number(bits)
        backbits     = number_to_bits(n, size)
        assert(bits == backbits)
        assert(table[n] is None)
        table[n] = bits

    for bits in table:
        print(''.join(str(b) for b in bits))