寻找给定特殊矩阵的行列式的Python程序

假设我们有一个n个顶点的树，其中每个顶点的标签从1到n。树的根具有标签1，每个顶点的权重为wi。现在形成一个nxn矩阵A，其中A(x,y) = Wf(x,y)，其中f(x,y)是顶点x和y的最小公共祖先。我们必须找出矩阵A的行列式。输入给定矩阵的边，权重和顶点总数。

因此，如果输入是input_array=[[1,2],[1,3],[1,4],[1,5]]，weights =[1,2,3,4,5]，vertices=5，则输出将为24。

矩阵A如下=

这个矩阵的行列式是24。

为了解决这个问题，我们将遵循以下步骤:

• w:=一个空列表
• 对于每个i在range(0,vertices)中，完成以下操作：
  • 将weights[i]和一个新列表添加到w中
• 对于每个i, item在enumerate(input_array)中，完成以下操作：
  • p:=item[0]
  • q:=item[1]
  • 在w[p-1,1]的末尾插入q-1
  • 在w[q-1,1]的末尾插入p-1
• det:=1
• stack:=一个包含一个元组(0,0)的栈
• 当stack不为空时，完成以下操作：
  • i,weights:=从顶部删除栈元素
  • det:=(det*(w[i,0]-weights)) mod (10^9+7)
  • 对于w[i,1]中的每个t，完成以下操作：
    • 添加包含(t,w[i,0])的元组到栈中
    • 对于w[i,1]中的每个t，完成以下操作：
    • 从w[t,1]中删除i
• 返回det

更多Python相关文章，请阅读：Python 教程

示例

让我们看下面的实现，以便更好地理解-

def solve(input_array, weights, vertices):
    w = [[weights[i],[]] for i in range(vertices)]
    for i, item in enumerate(input_array):
        p,q = item[0], item[1]
        w[p - 1][1].append(q - 1)
        w[q - 1][1].append(p - 1)
    det = 1
    stack = [(0,0)]
    while stack:
        i, weights = stack.pop()
        det = (det * (w[i][0] - weights)) % (10**9 + 7)
        stack += [(t,w[i][0]) for t in w[i][1]]
        for t in w[i][1]:
            w[t][1].remove(i)
    return det
print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))

输入

    [[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5

输出

    24