配列の要素の順位付けをしたい。

Question

前提

a=[12,43,7,15,9] の配列の要素を小さい順に並べたときのように順位で表示したいです。
a=[12,43,7,15,9]であれば、
出力結果は（2，4，0，3，1）です。

実現したいこと

個人的にはaの配列をソートして、新しい配列を作り、その配列の順番をaの配列に反映させるプログラムを作ってみたいと思っています。

下記のプログラムはソートしたとこで終わっています。
ここからどうすればいいでしょうか。

該当のソースコード

a=[12,43,7,15,9]

new_list=sorted(a)

//aの配列をソートした新しい配列の要素番号をaに対応付けしたい...

試したこと

ソートする方法とかはたくさんあると思うのですが、順位を反映させるというものが見つからず困ってます。

Comments

[jbpb0]

これ？
https://teratail.com/questions/180859

[lehshell]

SmaSTATION さん
a=[12,43,7,15,9] とありますが、リスト内に同じ数字があった場合の期待する出力結果を記載しましょう。
2人の方はそれぞれ異なる受け取り方をされています。

Answer 1

リスト内に重複する要素がない場合。

>>> a = [12, 43, 7, 15, 9] 
>>> [sorted(a).index(x) for x in a]
[2, 4, 0, 3, 1]

Answer 2

個人的にはaの配列をソートして、新しい配列を作り、その配列の順番をaの配列に反映させるプログラムを作ってみたいと思っています。

これを実現すると以下になります．

a = [12, 43, 7, 15, 9]
new_list = sorted(a)           # aの配列をソートして、新しい配列を作り

rank = [0] * len(a)
for i in range(len(new_list)): # その配列の順番を
    for j in range(len(a)):    # aの配列に
        if new_list[i] == a[j]:
            rank[j] = i        # 反映させる

print(rank) # [2, 4, 0, 3, 1]

配列の要素とその順番が一致しているかどうか判定するのに2重のループになっているため，要素数Nに対して時間計算量O(N^2)のアルゴリズムとなっており，非常に低速な実装です．また，要素に重複がある場合正しく動作しないので，もっとコードを書く必要があります．

この問題を解決すべく，ソートする際に，元の配列のインデックス情報の方を並び替えてしまえば良い，という発想が必要になります．ここではソートにかかる時間計算量そのままO(N log N)で済みます．

これは一般に，argsort()と呼ばれる動作になり，順位を求める実装と合わせて次のようになります．

def argsort(arr, reverse = False): # ソート前のindexを返す
    return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)

a = [12, 43, 7, 15, 9]
rank = [0] * len(a)
for r, idx in enumerate(argsort(a)): # r: 順位, idx: argsortで求めたソート前のindex
    rank[idx] = r                    # ソート前のindexであるidxを使ってrank配列のidx番目の順位をrにする
print(rank) # [2, 4, 0, 3, 1]

また，argsort()の実装方法はこれに限りません．あくまで一例です．他にも

def argsort(arr, reverse = False):
    return [x for x, y in sorted(enumerate(arr), key = lambda x: x[1], reverse = reverse)]

などがあります．なお基本構造はどれも同じで，ソートの対象keyの指定を，key = arr.__getitem__として値を指定するか，enumerate()で列挙される要素の1番目に対象の値があることを利用したkey = lambda x: x[1]とするなど，複数のテクニックが存在します．ソートの対象はリストの値，実際に並び替えられたのはリストのインデックス．といった具合です．

stack overflow - How to get indices of a sorted array in Python

今回はこれを使ってindexを保持したソートをすることで，O(N log N)の時間計算量で順位を反映させることができました．
このままだと同じ値でも別々の順位を割り振られる実装になっていますので，次のように変更することもできます．

rank = [0] * len(a)
rank_no = set()
for idx in argsort(a):
    rank_no.add(a[idx])
    rank[idx] = len(rank_no)

余談ですが「たまたま」例示いただいたデータ[12, 43, 7, 15, 9]においてargsort()の結果と求めた順位rankが同じになっています(非常にややこしいです)．argsort()の結果を例示しなかったのは混乱するからです...

結論

import random

def argsort(arr, reverse = False):
    return sorted(range(len(arr)), key = arr.__getitem__, reverse = reverse)

def calc_rank1(arr, reverse = False): # 重複があっても左から順に順位付け
    rank = [0] * len(arr)
    for r, idx in enumerate(argsort(arr, reverse)):
        rank[idx] = r
    return rank

def calc_rank2(arr, reverse = False): # 重複は同じ順位
    rank = [0] * len(arr)
    rank_no = set()
    for idx in argsort(arr, reverse):
        rank_no.add(arr[idx])
        rank[idx] = len(rank_no) - 1
    return rank

a = [random.randint(0, 20) for _ in range(10)]

print("original:", a)             # [9, 6, 9, 19, 9, 9, 15, 3, 10, 12]
print("argsort :", argsort(a))    # [7, 1, 0, 2, 4, 5, 8, 9, 6, 3]
print("rank1   :", calc_rank1(a)) # [2, 1, 3, 9, 4, 5, 8, 0, 6, 7]
print("rank2   :", calc_rank2(a)) # [2, 1, 2, 6, 2, 2, 5, 0, 3, 4]