# -*- coding: utf-8 -*-
# CodificacionHuffman.txt => CodificacionHuffman.py
#
# Codificación De Huffman
# Algoritmo De Codificación Con Entropía
# Comunicaciones Digitales
#
# Gilberto Stankiewicz
# ESCOM 4CM4
# http://www.stan.com.mx
# Marzo 2008
# Python 2.5

from __future__ import division # opcional, solo para realizar divisiones con flotantes

probabilidades = [0.175, 0.126, 0.084, 0.077, 0.063, 0.063, 0.049, 0.042, 0.042, 0.035, 0.035, 0.035, 0.028, 0.028, 0.028, 0.021, 0.021, 0.014, 0.014, 0.007, 0.007, 0.007] # tarea problema 18
#probabilidades = [0.35,0.25,0.15,0.15,0.1] # tarea problema 17
#probabilidades = [0.25,0.25,0.2,0.1,0.1,0.1] # tarea problema 16
#probabilidades = [7/36,4/36,4/36,3/36,2/36,2/36,2/36,2/36,2/36,2/36,1/36,1/36,1/36,1/36,1/36,1/36] # ejemplo 1 wikipedia http://en.wikipedia.org/wiki/Huffman_coding
#probabilidades = [0.10,0.15,0.30,0.16,0.29] # ejemplo 2 wikipedia http://en.wikipedia.org/wiki/Huffman_coding

# funciones
def huffmanIniciar(l):
    return [[x,""] for x in l]

def huffmanImprimir(l):
    for x in l:
        print "%.3f  %s" % tuple(x)
    print ""

def huffmanIterar(l):
    # ordenar descendentemente
    l.sort()
    l.reverse()
    # condición de paro
    if len(l) == 2:
        l[0][1] = "0"
        l[1][1] = "1"
        huffmanImprimir(l)
        return
    # guardar los últimos dos
    ultimo = l[-1][0]
    penultimo = l[-2][0]
    # sumar los últimos dos
    suma = ultimo + penultimo
    l[-2][0] = suma
    l.pop()
    # iterar
    huffmanIterar( l )
    # buscar primer valor igual a 'suma'
    for x in range(len(l)):
        if l[x][0] == suma:
            break
    l.append( [penultimo, l[x][1] + "0" ] )
    l.append( [ultimo, l[x][1] + "1" ] )
    l.pop( x )
    # imprimir
    huffmanImprimir( l )

def huffman(p):
    huffmanIterar( huffmanIniciar(p) )

# main
if __name__ == "__main__":
    huffman( probabilidades )