套汇问题 Python实现，算法设计，DFS深度遍历

# P67


# 套汇问题可以理解为一个有向图找出环的问题，
# 要想有盈利，需要所有的汇率乘积大于1
# 在贪心条件下，找到一个环路径上的乘积大于1就有套汇的可能性


"""
# 输入一个汇率表

    b1 b2 b3 b4
b1   k11  k12 k13 k14
b2   k21 k22 k23 k24
b3   k31 k32 k33 k34
b4   k41 k42 k43 k44

所有不支持兑换的币种均设置为 -1 ,
同币种设置为 -1，不考虑同币种之间的兑换
"""


def path_values(rates_, now_rate, path):
    """

    :param rates_: 利率表
    :param now_rate: 累乘的利率
    :param path: 兑换路径，连续两个表示一条路线
    :return:
    """
    if len(path) >= 2:
        return path_values(rates_, now_rate * rates_[path[0]][path[1]], path[1:])
    else:
        return now_rate


def find_path(rates_, path, start):
    """

    :param rates_: 利率表
    :param path: 路径
    :param start: 路径中最后一个起始点
    :return:
    """
    from copy import deepcopy
    path = deepcopy(path)

    if start in path:
        # 生成一条兑换路径并计算汇率
        path.append(start)
        values = path_values(rates_, 1, path)
        if values > 1:
            print(path, values)
            return
            # exit()  # 仅适用于IDE 环境
    path.append(start)
    # 如果这个可能的起始点不在路径中则加入路径中
    for i in range(len(rates_)):
        # 根据最后一个起始点继续寻找路径遍历表
        if rates_[start][i] > 0:
            find_path(rates_, path, start=i)


def find_values(rates_):
    for i in range(len(rates_)):
        find_path(rates_, [], i)


rates = [[-1, 0.7, -1],
         [-1, -1, 9.5],
         [0.16, -1, -1]]

find_values(rates)

输出

[0, 1, 2, 0] 1.0639999999999998
[1, 2, 0, 1] 1.0639999999999998
[2, 0, 1, 2] 1.0639999999999998