[アルゴリズム] ランキングづけの問題

モチベーション

ランキングづけのアルゴリズムの問題で少し悩んだので，少し考察してみました．
なお，単純化のため，個別のパターンの計算量最適化は考慮していません．
あくまで，ランキングづけ問題の複数のパターンを一般化して整理してみよう！というモチベーションです．

発想

すべての問題について，各参加者のエントリを定義することで，考えやすくなります．
エントリ内に必要な情報を，

• 入力される情報
• 参加者のランキング
• 出力時に必要な情報

の３つに分けて考えると良いかなと思います．

問題例

以下の各パターンでは，参加者のテストの点数が与えられるので，それをランクづけした上で，所定の形式で出力することが求められます．

例１

入力:参加者の名前とスコアの組が，順番に与えられる
出力:参加者の名前とそのランキングを，入力の順に出力する

# 入力　
shinji 60
rei 100
asuka 95
mari 80

# 出力
shinji 4
rei 1
asuka 2
mari 3

例2

入力:参加者の名前とスコアの組が，順番に与えられる
出力:参加者の名前を，ランキング順に出力する

# 入力　
shinji 60
rei 100
asuka 95
mari 80

# 出力
rei
asuka
mari
shinji

例3

入力:参加者のスコアが順番に与えられる
出力:ランキングを，入力の順に出力する

# 入力
60
100
95
80

# 出力
4
1
2
3

解答例

例1

入力:参加者の名前とスコアの組が，順番に与えられる
出力:参加者の名前とそのランキングを，入力の順に出力する

従って，エントリ内に必要な情報は

• 名前，テストの点数(=入力される情報)
• 参加者のランキング
• 入力時の順番(=出力時に必要な情報)

の３つです
したがって，各参加者のエントリは以下のように定義すると良いはずです．

# 入力直後
children=[
    {'name':'shinji','score':60,'rank':None,'id':0,},
    {'name':'rei','score':100,'rank':None,'id':1,}
    {'name':'asuka','score':95,'rank':None,'id':2,}
    {'name':'mari','score':80,'rank':None,'id':3,}
]

# ランクづけの処理を行う

# ランキングづけ後
children=[
    {'name':'shinji','score':60,'rank':4,'id':0,},
    {'name':'rei','score':100,'rank':1,'id':1,}
    {'name':'asuka','score':95,'rank':2,'id':2,}
    {'name':'mari','score':80,'rank':3,'id':3,}
]

入力が与えられた時点ではrankはNoneになっていますが，入力が全て与えられた後，各参加者のrankを計算する処理を実行すれば良いでしょう．
例１で重要なのは，出力時に，入力時の順番を覚えておく必要がある点です．
そのために，上記の配列childrenでは，各エントリに入力順(id)を定義しています

例２

入力:参加者の名前とスコアの組が，順番に与えられる
出力:参加者の名前を，ランキング順に出力する

従って，エントリ内に必要な情報は

• 名前，テストの点数(=入力される情報)
• 参加者のランキング

例１と基本的には同じですが，例２の場合は，出力時はランキング順に出力するので，入力時の順番は不要です．したがって，各参加者のエントリは以下のようになります．

# 入力直後
children=[
    {'name':'shinji','score':60,'rank':None},
    {'name':'rei','score':100,'rank':None}
    {'name':'asuka','score':95,'rank':None}
    {'name':'mari','score':80,'rank':None}
]

# ランクづけの処理を行う

# ランキングづけ後
children=[
    {'name':'shinji','score':60,'rank':4},
    {'name':'rei','score':100,'rank':1}
    {'name':'asuka','score':95,'rank':2}
    {'name':'mari','score':80,'rank':3}
]

例3

入力:参加者のスコアが順番に与えられる
出力:ランキングを，入力の順に出力する

従って，エントリ内に必要な情報は

• テストの点数(=入力される情報)
• 参加者のランキング
• 入力時の順番(=出力時に必要な情報)

です．
例１，２と違うのは，参加者の名前が不要ということです，
（名前のような）参加者固有の情報が与えられないので，「点数に対してランクづけする」という風に解釈してしまうと，頭がこんがらがります．
ですから，入力時の順番を参加者固有のidとして各エントリ内に保持して，出力時はidでソートすれば良いでしょう．

# 入力直後
children=[
    {'score':60,'rank':None,'id':0,},
    {'score':100,'rank':None,'id':1,}
    {'score':95,'rank':None,'id':2,}
    {'score':80,'rank':None,'id':3,}
]

# ランクづけの処理を行う

# ランキングづけ後
children=[
    {'score':60,'rank':4,'id':0,},
    {'score':100,'rank':1,'id':1,}
    {'score':95,'rank':2,'id':2,}
    {'score':80,'rank':3,'id':3,}
]

まとめ

入出力時に必要な情報をまとめて，エントリとして定義する　ことが重要．