Combinatorial encoding/decoding

combinatorial_encoding.py

import math


def bin_string(n, size):
  l = ['0'] * size
  for i in xrange(size):
    l[size - 1 - i] = '01'[n % 2]
    n /= 2
  return ''.join(l)


def gen_binomial_table(n):
  c = [[1] + [0] * (n - 1)]
  for i in xrange(1, n + 1):
    c.append([1] + [c[i - 1][j - 1] + c[i - 1][j] for j in xrange(1, n)])
  return c


def encode_rank_to_combination(rank, n):
  num_ones = n / 2
  codeword = 0
  while num_ones:
    n = num_ones - 1
    while choose_lookup[n + 1][num_ones] <= rank:
      n += 1
    codeword |= (1 << n)
    rank -= choose_lookup[n][num_ones]
    num_ones -= 1
  return codeword


def decode_combination_to_rank(codeword, n):
  num_ones = 1
  result = 0
  i = 0
  while codeword:
    if codeword & 1:
      result += choose_lookup[i][num_ones]
      num_ones += 1
    codeword >>= 1
    i += 1
  return result
    

if __name__ == '__main__':
  n = 12
  
  choose_lookup = gen_binomial_table(n)
  num_words = choose_lookup[n][n / 2]
  
  print '%.2f bits to %d balanced bits' % (math.log(num_words) / math.log(2.0), n)
  
  print
  print 'Printing coding table'
  codewords = [encode_rank_to_combination(i, n) for i in xrange(num_words)]
  for i, codeword in enumerate(codewords):
    print i, bin_string(codeword, n)
    
  print
  print 'Printing decoding table'
  for codeword in codewords:
    print bin_string(codeword, n), decode_combination_to_rank(codeword, n)