Реализация алгоритма Шеннона-Фано

p=[0.3, 0.2, 0.15, 0.1, 0.08, 0.07, 0.05, 0.04, 0.01]
codes=['']*len(p) 
 
 
#вариант функции №1
def shannon_fano_recursive(p, codes, code_prefix=''):
    if len(p) == 1:
        codes[0] = code_prefix
    else:
        left = []
        right = list(p)
        for i in p:
            if sum(left) < sum(p) / 2:
                left.append(i)
                right.remove(i)
            else:
                break
        shannon_fano_recursive(left, codes, code_prefix + '1')
        shannon_fano_recursive(right, codes, code_prefix + '0')
    return codes
print(shannon_fano_recursive(p, codes))
 
 
codes=['']*len(p)#восстанавливаю массив с кодами символов 
 
 
#вариант функции №2
def alg_ShennonaFano(x,y,p,codes):# на вход подаются индексы массива и сами массивы
    ver=0 # с началом каждого цикла рекурсии вероятность должна обнуляться
    for i in range(x,y):
        if abs(y-x)==2:#особый финальный случай, когда осталось всего два элемента
                codes[x]+='1'
                codes[y-1]+='0'
        else:
            k=abs(ver-sum(p[x:y])/2) #сохраняю разность предыдущей вероятности с суммой половины массива
            ver+=p[i] 
            if k<abs(ver-sum(p[x:y])/2): #ищем значение, наиболее близкое к половине суммы массива
            #разбиваем массив на две части по i, в одной части 1 в другой 0
                for j in range(x,i):
                    codes[j]+='1'
                    alg_ShennonaFano(x,i,p,codes)
                for g in range(i,y):
                    codes[g]+='0'
                alg_ShennonaFano(i,y,p,codes)
 
alg_ShennonaFano(0,9,p,codes)
print(codes)