代码之家 › 专栏 › 技术社区 › Nick

numpy:将矩阵提升到幂会产生奇怪的结果

numpy python-3.x

Nick · 技术社区 · 5 年前

我的解决方案 KnightDialer problem on Leetcode :

import numpy as np
class Solution:
  def knightDialer(self, N: int) -> int:
    M = np.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                   [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                   [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
                   [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
                   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                   [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
                   [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                   [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
                   [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]])
    return np.sum(M**(N-1)) % (10**9 + 7)

它适用于N值高达51的情况。例如,对于N=1,它正确地返回10,对于N=2,它正确返回20,对于N=3,它正确的返回46,以此类推;51它停止产生准确的结果(对于N=52,它返回107679695,而不是 690023703). 我不知道为什么,但不知何故将矩阵提高到幂>51导致结果不准确。

我试着替换 M**(N-1) 具有 np.linalg.matrix_power(M, (N-1)) 但输出仍然不准确。我的预感是,幕后有一些神秘的“魔法”,但我不确定是什么。

0 回复 | 直到 5 年前

user555045 5 年前

Numpy很难使用,因为它适用于固定大小的整数,例如 int32 或 int64 (这里使用哪一个取决于您的python安装)。像这样对矩阵进行指数化会使条目大于该数据类型的限制,从而导致截断。

对于常规Python整数,可以使用这种实现(先乘以矩阵,然后应用模约简),因为常规Python整数可以有更高的值。例如:

def mm(A, B):
    return [[sum([x*y for (x, y) in zip(row, col)]) for col in zip(*B)] for row in A]

def knightDialer(N: int) -> int:
    M = [[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
        [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
        [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]]
    N = N - 1
    res = [[int(i == j) for j in range(len(M))] for i in range(len(M))]
    while N:
        if N & 1: res = mm(res, M)
        M = mm(M, M)
        N >>= 1
    print(M)
    return sum([sum(i) for i in zip(*res)]) % (10**9 + 7)

在求幂过程中应用模约简可以让numpy矩阵在不耗尽比特的情况下工作:

def knightDialer(N: int) -> int:
    M = np.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
                   [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
                   [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
                   [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
                   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                   [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
                   [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
                   [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
                   [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]], dtype=np.int64)
    N = N - 1
    res = np.eye(M.shape[0], dtype=np.int64)
    while N:
        if N & 1: res = res * M % (10**9 + 7)
        M = M * M % (10**9 + 7)
        N >>= 1
    return np.sum(res) % (10**9 + 7)

使用 dtype=np.int64 如果安装时默认整数类型为 int32 . int32 足够容纳以下数字 10**9 + 7 ,但在矩阵乘法过程中,两个这样的数字之间会有乘积(然后它们也会被求和),如果 int32 被使用。