CODEWITHSUNDEEP
pythonarraysalgorithmlistsorting
Max Matti
Max Matti

Reputation: 433

How to replace numbers with order in (python) list

I have a list containing integers and want to replace them so that the element which previously contained the highest number now contains a 1, the second highest number set to 2, etc etc.

Example: [5, 6, 34, 1, 9, 3] should yield [4, 3, 1, 6, 2, 5].

I personally only care about the first 9 highest numbers by I thought there might be a simple algorithm or possibly even a python function to do take care of this task?

Edit: I don't care how duplicates are handled.

Upvotes: 4

Views: 3014

Answers (5)

9000
9000

Reputation: 40894

A short, log-linear solution using pure Python, and no look-up tables.

The idea: store the positions in a list of pairs, then sort the list to reorder the positions.

enum1 = lambda seq: enumerate(seq, start=1)  # We want 1-based positions

def replaceWithRank(xs):
    # pos = position in the original list, rank = position in the top-down sorted list.
    vp = sorted([(value, pos) for (pos, value) in enum1(xs)], reverse=True)
    pr = sorted([(pos, rank) for (rank, (_, pos)) in enum1(vp)])
    return [rank for (_, rank) in pr]

assert replaceWithRank([5, 6, 34, 1, 9, 3]) == [4, 3, 1, 6, 2, 5]

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476594

A fast way to do this is to first generate a list of tuples of the element and its position:

sort_data = [(x,i) for i,x in enumerate(data)]

next we sort these elements in reverse:

sort_data = sorted(sort_data,reverse=True)

which generates (for your sample input):

>>> sort_data
[(34, 2), (9, 4), (6, 1), (5, 0), (3, 5), (1, 3)]

and nest we need to fill in these elements like:

result = [0]*len(data)
for i,(_,idx) in enumerate(sort_data,1):
    result[idx] = i

Or putting it together:

def obtain_rank(data):
    sort_data = [(x,i) for i,x in enumerate(data)]
    sort_data = sorted(sort_data,reverse=True)
    result = [0]*len(data)
    for i,(_,idx) in enumerate(sort_data,1):
        result[idx] = i
    return result

this approach works in O(n log n) with n the number of elements in data.

A more compact algorithm (in the sense that no tuples are constructed for the sorting) is:

def obtain_rank(data):
    sort_data = sorted(range(len(data)),key=lambda i:data[i],reverse=True)
    result = [0]*len(data)
    for i,idx in enumerate(sort_data,1):
        result[idx] = i
    return result

Upvotes: 8

akuiper
akuiper

Reputation: 214957

Another option, you can use rankdata function from scipy, and it provides options to handle duplicates:

from scipy.stats import rankdata

lst = [5, 6, 34, 1, 9, 3]
rankdata(list(map(lambda x: -x, lst)), method='ordinal')
# array([4, 3, 1, 6, 2, 5])

Upvotes: 4

falsetru
falsetru

Reputation: 369064

Using numpy.argsort:

numpy.argsort returns the indices that would sort an array.

>>> xs = [5, 6, 34, 1, 9, 3]

>>> import numpy as np
>>> np.argsort(np.argsort(-np.array(xs))) + 1
array([4, 3, 1, 6, 2, 5])

Upvotes: 3

Ma0
Ma0

Reputation: 15204

Assuimg you do not have any duplicates, the following list comprehension will do:

lst = [5, 6, 34, 1, 9, 3]
tmp_sorted = sorted(lst, reverse=True)  # kudos to @Wondercricket
res = [tmp_sorted.index(x) + 1 for x in lst]  # [4, 3, 1, 6, 2, 5]

To understand how it works, you can break it up into pieces like so:

lst = [5, 6, 34, 1, 9, 3]
# let's see what the sorted returns
print(sorted(lst, reverse=True))  # [34, 9, 6, 5, 3, 1]
# biggest to smallest. that is handy.
# Since it returns a list, i can index it. Let's try with 6
print(sorted(lst, reverse=True).index(6))  # 2
# oh, python is 0-index, let's add 1
print(sorted(lst, reverse=True).index(6) + 1)  # 3
# that's more like it. now the same for all elements of original list

for x in lst:
    print(sorted(lst, reverse=True).index(x) + 1)  # 4, 3, 1, 6, 2, 5

# too verbose and not a list yet..
res = [sorted(lst, reverse=True).index(x) + 1 for x in lst]
# but now we are sorting in every iteration... let's store the sorted one instead
tmp_sorted = sorted(lst, reverse=True)
res = [tmp_sorted.index(x) + 1 for x in lst]

Upvotes: 3

Related Questions