Pythonで分数のリストを誤差なしでソートする

はじめに

　AtCoder Beginner Contest 225 (ABC 225) の E 問題 で、表題のことができずに詰んだので、勉強した結果をまとめます。

普通にソートするときの問題点

　分数のリストをソートしたいときは、普通は以下のように分数を少数に直し、小数のリストでソートしますよね。

l = [5 / 7, 3 / 8, 1 / 2]
# l = [0.7142857142857143, 0.375, 0.5]

l = sorted(l)
# l = [0.375, 0.5, 0.7142857142857143]

　しかし、分母・分子の値が大きくなってくると誤差が出ることがあります。それが原因で、正しく順序がソートされないことがあるのです。誤差が出るパターンを1つ示します。

>>> (10 ** 9 + 1) / 10 ** 9
1.000000001

>>> 10 ** 9 / (10 ** 9 - 1)
1.000000001

$(10^9 + 1) / 10^9$ と $10^9 / (10^9 - 1)$ は異なるにもかかわらず、小数で表すと等しくなってしまいます。
　これを避けるためには小数を登場させなければいいです。つまり、 $x_a / y_a$ という分数が $x_b / y_b$ という分数より小さいかどうかを調べるときは、$x_a / y_a < x_b / y_b$ の真偽を確かめるのではなく、 $x_a \times y_b < x_b \times y_a$ の真偽を確かめればよいです。

>>> (10 ** 9 + 1) / 10 ** 9 == 10 ** 9 / (10 ** 9 - 1)
True
# 本当は等しくない

>>> (10 ** 9 + 1) * (10 ** 9 - 1) < 10 ** 9 * 10 ** 9
True
# 大小が正しく判定される

誤差なしでソートする方法

　組み込みの sorted() 関数の key 引数に functools.cmp_to_key(cmp) を渡してやることで、自前の cmp() 関数で定義した比較関数に従って、ソートすることができます。
　cmp_to_key() については こちら を参考にしました。

from functools import cmp_to_key

def cmp(a, b):  # a = [x_a, y_a], b = [x_b / y_b]
    # 比較対象の分数 a と b が等しければ 0 を返す
    if a[0] * b[1] == b[0] * a[1]:
        return 0
    # a, bという順で並んでほしい条件のときは-1を返し、それ以外では1を返す
    return -1 if a[0] * b[1] < b[0] * a[1] else 1

l = [[5, 7], [3, 8], [1, 2]]  # リストの各要素は [分子, 分母] とする
l = sorted(l, key=cmp_to_key(cmp))
# l = [[3, 8], [1, 2], [5, 7]]

　最後までご覧いただきありがとうございます。