Итерация над python OrderedDict

У меня есть следующий OrderedDict:

OrderedDict([('r', 1), ('s', 1), ('a', 1), ('n', 1), ('y', 1)])

Это фактически представляет собой частоту буквы в слове.

В первом шаге - я бы взял последние два элемента, чтобы создать объединенный кортеж, подобный этому;

 pair1 = list.popitem()
    pair2 = list.popitem()
    merge_list = (pair1[0],pair2[0])
    new_pair = {}
    new_pair[merge_list] = str(pair1[1] + pair2[1])
    list.update(new_pair);

Это создало для меня следующий OrderedList:

OrderedDict([('r', 1), ('s', 1), ('a', 1), (('y', 'n'), '2')])

Я хотел бы теперь перебирать элементы, каждый раз принимая последние три и решая на основе нижней суммы значений, что является объединенным объектом.

Например, приведенный выше список будет выглядеть следующим образом:

OrderedDict([('r', 1), (('s', 'a'), '2'), (('y', 'n'), '2')])

но выше было:

OrderedDict([ ('r', 1), ('s', 2), ('a', 1), (('y', 'n'), '2')])

Результат:

OrderedDict([('r', 1), ('s', 2), (('a','y', 'n'), '3')])

поскольку я хочу, чтобы левые имели меньшее значение

Я попытался сделать это сам, но не понял, как итерации от конца до начала над OrderedDict.

Как я могу это сделать?

EDITED Отвечая на комментарий:

Я получаю словарь частоты буквы в предложении:

{ 's':1, 'a':1, 'n':1, 'y': 1}

и нужно создать из него дерево хаффмана.

например:

((s,a),(n,y))

Я использую python 3.3

Ответы

Ответ 1

Простой пример

from collections import OrderedDict

d = collections.OrderedDict()
d['a'] = 1
d['b'] = 2
d['c'] = 3

for key, value in d.items():
    print key, value

Вывод:

a 1
b 2
c 3

Ответ 2

как перебирать от конца к началу над OrderedDict?

Или:

z = OrderedDict( ... )
for item in z.items()[::-1]:
   # operate on item

Или:

z = OrderedDict( ... )
for item in reversed(z.items()):
   # operate on item

Ответ 3

Обратите внимание, что, как отмечено в комментариях adsmith, это, вероятно, экземпляр XY Problem, и вы должны пересмотреть свои структуры данных.

Сказав это, если вам нужно работать только с тремя последними элементами, вам не нужно итерации. Например:

MergeInfo = namedtuple('MergeInfo', ['sum', 'toMerge1', 'toMerge2', 'toCopy'])

def mergeLastThree(letters):
    if len(letters) < 3:
        return False

    last = letters.popitem()
    last_1 = letters.popitem()
    last_2 = letters.popitem()

    sum01 = MergeInfo(int(last[1]) + int(last_1[1]), last, last_1, last_2)
    sum12 = MergeInfo(int(last_1[1]) + int(last_2[1]), last_1, last_2, last)
    sum02 = MergeInfo(int(last[1]) + int(last_2[1]), last, last_2, last_1)

    mergeInfo = min((sum01, sum12, sum02), key = lambda s: s.sum)

    merged = ((mergeInfo.toMerge1[0], mergeInfo.toMerge2[0]), str(mergeInfo.sum))

    letters[merged[0]] = merged[1]
    letters[mergeInfo.toCopy[0]] = mergeInfo.toCopy[1]

    return True

Тогда, имея:

letters = OrderedDict([('r', 1), ('s', 1), ('a', 1), ('n', 1), ('y', 1)])

print letters
mergeLastThree(letters)
print letters
mergeLastThree(letters)
print letters

Выдает:

>>> OrderedDict([('r', 1), ('s', 1), ('a', 1), ('n', 1), ('y', 1)])
OrderedDict([('r', 1), ('s', 1), (('y', 'n'), '2'), ('a', 1)])
OrderedDict([('r', 1), (('a', 's'), '2'), (('y', 'n'), '2')])

И чтобы полностью объединить всю структуру, вам нужно просто:

print letters
while mergeLastThree(letters):
    pass
print letters

Что дает:

>>> OrderedDict([('r', 1), ('s', 1), ('a', 1), ('n', 1), ('y', 1)])
OrderedDict([((('a', 's'), 'r'), '3'), (('y', 'n'), '2')])
>>>

Ответ 4

Вы можете выполнять итерацию с помощью enumerate и iteritems:

dict = OrderedDict()
# ...

for i, (key, value) in enumerate(dict.iteritems()):
    # Do what you want here