पायथन में करेंसी आर्बिट्रेज ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास करेंसी एक्सचेंज दरों का N x N टेबल है। हमें जांचना है कि क्या ट्रेड का कोई अनुक्रम मौजूद है जिससे किसी करेंसी की कुछ राशि A से शुरू करके उसी करेंसी की अधिक राशि प्राप्त की जा सके। कोई लेनदेन लागत नहीं है और हम आंशिक मात्राओं में भी ट्रेड कर सकते हैं।

उदाहरण के लिए, दिए गए मैट्रिक्स के लिए आउटपुट True होगा (आर्बिट्रेज मौजूद है)।

एल्गोरिदम (बेलमैन-फोर्ड / फ्लॉयड-वार्शल लॉग ट्रांसफॉर्म के साथ)

• प्रत्येक विनिमय दर matrix[i][j] को -log2(matrix[i][j]) में बदलें
• फ्लॉयड-वार्शल एल्गोरिदम चलाएं: matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])
• यदि विकर्ण पर कोई matrix[i][i] < 0 है, तो True वापस करें (नकारात्मक चक्र = आर्बिट्रेज)

उदाहरण

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(v):
            for i in range(v):
                for j in range(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))

इनपुट

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

आउटपुट

True