1

I am trying to write a code that replicates greedy algorithm and for that I need to make sure that my calculations use the highest value possible. Potential values are presented in a dictionary and my goal is to use largest value first and then move on to lower values. However since dictionary values are not sequenced, in for loop I am getting unorganized sequences. For example, out put of below code would start from 25.

How can I make sure that my code is using a dictionary yet following the sequence of (500,100,25,10,5)? 

a={"f":500,"o":100,"q":25,"d":10,"n":5}  
for i in a:
    print a[i]
Lorientas
  • 66
  • 6

4 Answers4

3

Two ideas spring to mind:

  1. Use collections.OrderedDict, a dictionary subclass which remembers the order in which items are added. As long as you add the pairs in descending value order, looping over this dict will return them in the right order.

  2. If you can't be sure the items will be added to the dict in the right order, you could construct them by sorting:

    • Get the values of the dictionary with values()
    • Sort by (ascending) value: this is sorted(), and Python will default to sorting in ascending order
    • Get them by descending value instead: this is reverse=True

    Here's an example:

    for value in sorted(a.values(), reverse=True):
    print value
alexwlchan
  • 5,699
  • 7
  • 38
  • 49
3

Dictionaries yield their keys when you iterate them normally, but you can use the items() view to get tuples of the key and value. That'll be un-ordered, but you can then use sorted() on the "one-th" element of the tuples (the value) with reverse set to True:

a={"f":500,"o":100,"q":25,"d":10,"n":5}  
for k, v in sorted(a.items(), key=operator.itemgetter(1), reverse=True):
    print(v)

I'm guessing that you do actually need the keys, but if not, you can just use values() instead of items(): sorted(a.values(), reverse=True)

LexyStardust
  • 1,018
  • 5
  • 18
  • It is a vending machine simulator and its goal is to pay back using least amount of changes. Types, values and quantity of available money is stored in a dictionary. In order to define the least amount of change, I run a loop and pay back the change. My loop needs to figure out the least number of changes I need. – Lorientas Aug 12 '15 at 14:32
  • I don't need the keys in this case so second part of the answer will be more relevant. – Lorientas Aug 12 '15 at 14:35
  • 2
    `key=operator.itemgetter(1)` is more efficient than the equivalent `lambda` expression. – chepner Aug 12 '15 at 14:35
  • @chepner You're quite right, although in my testing, not by as much as I thought it was going to be. I'll update the answer anyway. – LexyStardust Aug 12 '15 at 15:12
  • @Lorientas muddyfish is correct, I was actually asking LexyStardust to explain their answer. Your answer had a good amount of explanation! – SuperBiasedMan Aug 13 '15 at 08:14
1

You can use this

>>> a={"f":500,"o":100,"q":25,"d":10,"n":5}
>>> for value in sorted(a.itervalues(),reverse=True):
...     print value
... 
500
100
25
10
5
>>>
chandu
  • 1,053
  • 9
  • 18
-1
a={"f":500,"o":100,"q":25,"d":10,"n":5}
k = sorted(a, key=a.__getitem__, reverse=True)
v = sorted(a.values(), reverse=True)
sorted_a = zip(k,v)
print (sorted_a)

Output:

[('f', 500), ('o', 100), ('q', 25), ('d', 10), ('n', 5)]
Joe T. Boka
  • 6,554
  • 6
  • 29
  • 48
  • 2
    It seems that you're doing twice as much work as is necessary by sorting the keys and the values separately. Just sort the items, as in the other answers. – jme Aug 12 '15 at 14:24
  • Please explain what your code does and why it will solve the problem. An answer that just contains code (even if it's working) usually wont help the OP to understand their problem. – SuperBiasedMan Aug 13 '15 at 08:43
  • @SuperBiasedMan Good point! I was in a hurry and by the time I was ready to write an explanation the OP already accepted an other answer. However, I do believe that my answer could help the OP even without the explanation. And, I certainly believe that down-voting an otherwise good answer just because I didn't give an explanation is a little bit strange. – Joe T. Boka Aug 13 '15 at 08:54