Simulating a bad encoding of subsets

foo.py

#!/usr/bin/env python
import sys
import math

chosen = set()

def choose(n, k):
    return math.gamma(n+1) / (math.gamma(k+1) * math.gamma(n-k+1))

def yield_all_choices(n, k):
    def f(n, k, i=0, chosen=set()):
        if k == 0 or n == i:
            yield ()
            return

        # either choose i
        for t in f(n, k-1, i+1, set([i]).union(chosen)):
            yield (i, ) + t
        
        # or don't choose i
        for t in f(n, k, i+1, chosen):
            yield t
    
    for t in f(n, k, 0, set()):
        if len(t) == k:
            yield t

def elias_encode(n):
    b = bin(n)[2:]
    return '0' * (len(b) - 1) + b

def clever_encode(t):
    t = sorted((0,) + t)
    x = [n - p for (n, p) in zip(t[1:], t[:-1])]
    x = [elias_encode(i) for i in x]
    return "".join(x)

d = {}
if __name__ == '__main__':
    n = int(sys.argv[1])
    k = int(sys.argv[2])
    total = choose(n, k)
    i = 0
    for choice in yield_all_choices(n, k):
        i = i + 1
        if i % 100000 == 0:
            sys.stderr.write("\r                                 \r%.3f %%, %d total" % (i / total * 100, i))
        l = len(clever_encode(choice))
        d[l] = d.get(l, 0) + 1
    v = sorted(d.items())
    print
    print "Worst-case:", max(t[0] for t in v)
    print "Average-case:", sum(t[0] * t[1] for t in v) / total
    print "lower bound: %.3f" % math.log(total, 2)
    # print clever_encode((1, 3, 5, 7, 9))

results.csv

results.txt

$ python foo.py 32 1                                                                                                                        
Worst-case: 9
Average-case: 7.125
lower bound: 5.000

$ python foo.py 32 2                                                                                                                        
Worst-case: 16
Average-case: 12.1451612903
lower bound: 8.954

$ python foo.py 32 3                                                                                                                        
Worst-case: 21
Average-case: 15.975
lower bound: 12.276

$ python foo.py 32 4                                                                                                                        
Worst-case: 26
Average-case: 19.075862069
lower bound: 15.134

$ python foo.py 32 5                                                                                                                        
Worst-case: 29
Average-case: 21.6811735261
lower bound: 17.620

$ python foo.py 32 6                                                                                                                        
Worst-case: 32
Average-case: 23.9145346681
lower bound: 19.789

$ python foo.py 32 7                                                                                                                        
Worst-case: 35
Average-case: 25.8483416997
lower bound: 21.683

$ python foo.py 32 8                                                                                                                        
Worst-case: 38
Average-case: 27.5310375251
lower bound: 23.326