Positional Rankings And Dealing With Ties In Python
(I apologize that previous versions of this question displayed the wrong function that I need to fix, this has been remedied and I hope the question makes a little more sense now.)
Solution 1:
>>>sorted_scores = [... ('Apolo Ohno', 0),... ('Shanie Davis', -1),... ('Bodie Miller', -2),... ('Lindsay Vohn', -3), ... ('Shawn White', -3),... ('Bryan Veloso',-4)...]>>>>>>res = {}>>>prev = None>>>for i,(k,v) inenumerate(sorted_scores):...if v!=prev:... place,prev = i+1,v... res[k] = place...>>>print res
{'Apolo Ohno': 1, 'Bryan Veloso': 6, 'Shanie Davis': 2, 'Lindsay Vohn': 4, 'Bodie Miller': 3, 'Shawn White': 4}
Remember that dicts are unordered, so to iterate in order of place, you need to do this
>>> from operator import itemgetter
>>> printsorted(res.items(),key=itemgetter(1))
[('Apolo Ohno', 1), ('Shanie Davis', 2), ('Bodie Miller', 3), ('Lindsay Vohn', 4), ('Shawn White', 4), ('Bryan Veloso', 6)]
Solution 2:
=== Update after change/clarification of specs ===
# coding: asciidefranks_from_scores(sorted_scores):
"""sorted_scores: a list of tuples (object_id, score), sorted by score DESCENDING
return a mapping of object IDs to ranks
"""
ranks = {}
previous_score = object()
for index, (obj_id, score) inenumerate(sorted_scores):
if score != previous_score:
previous_score = score
rank = index + 1
ranks[obj_id] = rank
return ranks
from operator import itemgetter
import pprint
scores0 = dict([
('Apolo Ohno', 0),
('Shanie Davis', -1),
('Bodie Miller', -2),
('Lindsay Vohn', -3),
('Shawn White', -3)
])
scores1 = {
'lorem': 100,
'ipsum': 200,
'dolor': 300,
'sit': 300,
'amet': 300,
'quia': 400,
'consectetur': 500,
'adipiscing': 500,
'elit': 600,
}
scores2 = {
'lorem': 100,
'ipsum': 200,
'dolor': 300,
'sit': 300,
'amet': 300,
'quia': 400,
'consectetur': 500,
'adipiscing': 500,
'elit': 6000,
}
import pprint
funcs = (ranks_from_scores, ) # Watch this space!
tests = (scores0, scores1, scores2)
for test in tests:
print
test_list = sorted(test.items(), key=itemgetter(1), reverse=True)
print"Input:", test_list
for func in funcs:
result = func(test_list)
print"%s ->" % func.__name__
pprint.pprint(result)
Results:
Input: [('Apolo Ohno', 0), ('Shanie Davis', -1), ('Bodie Miller', -2), ('Lindsay
Vohn', -3), ('Shawn White', -3)]
ranks_from_scores ->
{'Apolo Ohno': 1,
'Bodie Miller': 3,
'Lindsay Vohn': 4,
'Shanie Davis': 2,
'Shawn White': 4}
Input: [('elit', 600), ('consectetur', 500), ('adipiscing', 500), ('quia', 400),
('dolor', 300), ('sit', 300), ('amet', 300), ('ipsum', 200), ('lorem', 100)]
ranks_from_scores ->
{'adipiscing': 2,
'amet': 5,
'consectetur': 2,
'dolor': 5,
'elit': 1,
'ipsum': 8,
'lorem': 9,
'quia': 4,
'sit': 5}
Input: [('elit', 6000), ('consectetur', 500), ('adipiscing', 500), ('quia', 400)
, ('dolor', 300), ('sit', 300), ('amet', 300), ('ipsum', 200), ('lorem', 100)]
ranks_from_scores ->
{'adipiscing': 2,
'amet': 5,
'consectetur': 2,
'dolor': 5,
'elit': 1,
'ipsum': 8,
'lorem': 9,
'quia': 4,
'sit': 5}
=== original submission ===
This code assumes that you really want the highest score to get rank 1, not the lowest score getting rank 1 (or 0!).
# coding: asciidefranks_from_scores(scores, debug=False):
"""scores (a mapping of object IDs to scores)
return a mapping of object IDs to ranks
"""
alist = [(v, k) for k, v in scores.items()]
alist.sort(reverse=True)
if debug: print'alist:', alist
bdict = {}
previous_score = object()
for posn, (score, obj_id) inenumerate(alist):
if score != previous_score:
previous_score = score
rank = posn + 1
bdict[obj_id] = rank
if debug:
print'bdict:', bdict
blist = [(v, k) for k, v in bdict.items()]
print'blist:', sorted(blist)
return bdict
ranks_from_scores(
{'q': 10, 'w': 20, 'e': 20, 'r': 20, 't': 30},
debug=True,
)
Output:
alist: [(30, 't'), (20, 'w'), (20, 'r'), (20, 'e'), (10, 'q')]
bdict: {'q': 5, 'r': 2, 'e': 2, 't': 1, 'w': 2}
blist: [(1, 't'), (2, 'e'), (2, 'r'), (2, 'w'), (5, 'q')]
Solution 3:
The way to do this is not to calculate the element's position is some arbitrary sequence, but rather to calculate how many other elements have a better score.
EDIT:
By popular demand, O(n)'ed and everything:
positions = {}
cur_score = None # Score we're examining
cur_count = 0 # Number of others that we've seen with this score
for ix, (name, score) in enumerate(sorted_scores):
if score == cur_score: # Same score for this player as previous
cur_count += 1
else: # Different score from before
cur_score = score
cur_count = 0
positions[name] = ix - cur_count + 1 # Add 1 because ix is 0-based
print positions
Solution 4:
Looks like you can use the sorted and enumerate builtins, the groupby method from itertools and the itemgetter method from operator. Assumes higher scores are better... (if lower scores are better, change reverse=True to reverse=False)
>>>from itertools import groupby>>>from operator import itemgetter>>>scores = {...'lorem': 100,...'ipsum': 200,...'dolor': 300,...'sit': 300,...'amet': 300,...'quia': 400,...'consectetur': 500,...'adipiscing': 500,...'elit': 600,... }>>>sorted_items = sorted(scores.items(), key=itemgetter(1), reverse=True)>>>groups = groupby(sorted_items, itemgetter(1))>>>for rank, (score, items) inenumerate(groups):...print rank+1, map(itemgetter(0), items)...
1 ['elit']
2 ['consectetur', 'adipiscing']
3 ['quia']
4 ['dolor', 'sit', 'amet']
5 ['ipsum']
6 ['lorem']
Solution 5:
Solution
Here's one simple way to do it by modifying your code a little rather than importing modules:
prev = None
rank = 0
incr = 1
positions = {}
for key, value in sorted_list:
if value is not None:
if value != prev:
rank += incr
incr = 1
else:
incr += 1
positions[key] = rank
prev = value
A Test
For
sorted_list = [
('Apolo Ohno', 0),
('Shanie Davis', -1),
('Bodie Miller', -2),
('Lindsay Vohn', -3),
('Shawn White', -3),
('Bryan Veloso',-4)
]
I get positions as:
{'Apolo Ohno': 1,
'Shanie Davis': 2,
'Bodie Miller': 3,
'Lindsay Vohn': 4,
'Shawn White': 4,
'Bryan Veloso': 6}
which I think is what you are going for even though you aren't quite clear about whether there should be a 6 after the two 4's.
Post a Comment for "Positional Rankings And Dealing With Ties In Python"