Pythonで通貨裁定取引を見つけるプログラム

為替レートのNxNテーブルが1つあるとします。取引のシーケンスがあるかどうかを確認する必要があります。これで、任意の通貨のAの金額から始めて、その通貨のAよりも大きい金額になる可能性があります。取引コストはなく、小数の取引も可能です。

このマトリックスのエントリ[I、j]の値は、1単位の通貨iで購入できる通貨jの量を表します。ここで、通貨0がUSD、1がCAD、2がEURであると考えてください。次のように裁定取引を行うことができます-

• 1カナダドルを0.65ユーロで売る

• 0.65ユーロを0.7865米ドル（0.65 * 1.21）で売る

• 1.00672 CAD（0.65 * 1.21 * 1.28）で0.7865米ドルを売る

したがって、入力が次のような場合

その場合、出力はTrueになります。

これを解決するには、次の手順に従います-

• 0から行列のサイズまでの範囲のiについては、次のようにします

  • 0からmatrix[0]のサイズまでの範囲のjの場合、実行

    • matrix [i、j]：=−log base 2 value of（matrix [I、j]）

• v：=行列の行数

• 0からvの範囲のkについては、次のようにします

  • 0からvの範囲のiの場合、実行

    • 0からvの範囲のjについては、次のようにします

      • matrix [I、j]：=matrix [I、j]と（matrix [I、k] + matrix [k、j]）の最小値

• 行列の対角線の項目のいずれかがゼロ以外の場合はTrueを返します。

理解を深めるために、次の実装を見てみましょう-

Python

import math
class Solution:
   def solve(self, matrix):
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            matrix[i][j] = −math.log(matrix[i][j], 2)
   v = len(matrix)
   for k in range(0, v):
      for i in range(0, v):
         for j in range(0, v):
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
   return any(matrix[i][i] < 0 for i in range(len(matrix)))
ob = Solution()
matrix = [
   [1, 1.28, 0.82],
   [0.78, 1, 0.65],
   [1.21, 1.55, 1]
]
print(ob.solve(matrix))

入力

matrix = [
   [1, 1.28, 0.82],
   [0.78, 1, 0.65],
   [1.21, 1.55, 1]
]

出力

True