compressing permuations by using elimination coding

compress_permuation_by_index.py

import math
from functools import reduce


def bit_count(x):
    """ The minimum bits needed to represent a number """
    # return math.ceil(math.log(x + 1) / math.log(2))
    return math.ceil(math.log2(x))


def initial(data):
    largest_number = max(data)
    bits = bit_count(largest_number)
    print('\n')
    print("Encoding this by the number values in the set, with %d bits, dictated by the max value %d, yields:" % (bits, largest_number))
    print(reduce(lambda x, y: '%s%s' % (x, "{0:03b} ".format(y)), data, ''))
    print('%s bits' % (len(data) * bits))


def index_encoded(data):
    print('\n')
    print('Now lets encode by index')
    # create output
    output = ''
    # create an array of the amount of data, populate it
    l = sorted(data)
    for num in data:
        # find the index of the slot with the value of our number
        index = l.index(num)
        # determine how many bits needed to encode the free slot index
        # we do this by taking length of array of data
        bits_needed = bit_count(len(l))
        # add to output stream
        output += "{0:0{1}b} ".format(index, bits_needed)
        # remove the slot from the array
        del l[index]
    print(output)
    print('%s bits' % sum(c != ' ' for c in output))


def main(data):
    """ compressing permuations by using elimination coding """
    initial(data)
    index_encoded(data)


if __name__ == '__main__':
    main([5, 7, 1, 4, 6, 3, 2, 0])

output

Encoding this by the number values in the set, with 3 bits, dictated by the max value 7, yields:
101 111 001 100 110 011 010 000 
24 bits


Now lets encode by index
101 110 001 011 11 10 1 0 
18 bits