Iterate over OrderedDict in Python

Question

I have the following OrderedDict:

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

This actually presents a frequency of a letter in a word.

In the first step - I would take the last two elements to create a union tuple like this;

 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);

This created for me the following OrderedList:

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

I would like now to iterate over the elements, each time taking the last three and deciding based on the lower sum of the values what is the union object.

For instance the above list will turn to;

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

but the above was:

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

The result would be:

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

as I want the left ones to have the smaller value

I tried to do it myself but doesn't understand how to iterate from end to beginning over an OrderedDict.

How can I do it?

EDITED Answering the comment:

I get a dictionary of frequency of a letter in a sentence:

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

and need to create a huffman tree from it.

for instance:

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

I am using python 3.3

Answer 1

how to iterate from end to beginning over an OrderedDict ?

Either:

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

Or:

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

Answer 2

Note that, as noted in the comments by adsmith, this is probably an instance of an XY Problem and you should reconsider your data structures.

Having said that, if you need to operate only on last three elements, then you don't need to iterate. For example:

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

Then having:

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

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

Produces:

>>> 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')])

And to merge the whole structure completely you need to just:

print letters
while mergeLastThree(letters):
    pass
print letters

Which gives:

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

Answer 3

Simple example

from collections import OrderedDict

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

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

Output:

a 1
b 2
c 3

Answer 4

For Python 3.x

d = OrderedDict( ... )

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

---

For Python 2.x

d = OrderedDict( ... )

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

Answer 5

You can iterate using enumerate and iteritems:

dict = OrderedDict()
# ...

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