按指定方式将矩阵值分解为两个数

Question

我有一个矩阵，里面有一些数字（那些不是None的），比如6、9、9、3、5和4。我想把这些数字拆分成两个数字，使它们加起来等于原来的数字。

matrix_aux = [
[None,    6, None,    9],
[   9, None,    3, None],
[None,    5,    4, None]
]

为了实现这个拆分，我需要在一个叫matrix_aux的矩阵里多加一列，然后再加一行，这样就可以对原来的matrix_aux里的数字进行拆分了。

拆分的结果应该像这样，确保所有的拆分都遵循之前已经做过的拆分。这将是一个正确的输出：

matrix_aux_with_num_decompositions = [
[None,    6, None,    9,    4],
[   9, None,    3, None,    2],
[None,    5,    4, None,    3],

[   7,    2,    1,    5      ]
]

注意，所有的拆分结果之间是相互一致的，

decomposed numerical value = row decomposition + column decomposition
6 = 4 + 2
9 = 4 + 5
9 = 2 + 7
3 = 2 + 1
5 = 3 + 2
4 = 3 + 1

要解决这个问题，我觉得你需要用到一些技术，比如回溯法和动态更新数组。

# Function to decompose a number into two numbers that sum up to that value
def decompose_number(number, previous_decompositions):
    for i in range(1, number):
        complement = number - i
        if i not in previous_decompositions.values() and complement not in previous_decompositions.values():
            return i, complement

# Find numeric values and their decompositions
decompositions = {}
for row in aux_matrix:
    for element in row:
        if element is not None:
            if element not in decompositions:
                decompositions[element] = decompose_number(element, decompositions)

# Add an additional column to the matrix
for row in aux_matrix:
    row.append(None)

# Add an additional row for decompositions
aux_matrix.append([None] * len(aux_matrix[0]))

# Add values and decompositions to the matrix
for i, row in enumerate(aux_matrix[:-1]):
    for j, element in enumerate(row[:-1]):
        if element is not None:
            row[-1] = decompositions[element][0]
            aux_matrix[-1][j] = decompositions[element][1]

for row in aux_matrix:
    print(row)

我试过这个代码，但它给我的拆分结果是相互矛盾的，比如这里说3 = 3 + 1，这显然是不对的。

[None,    6, None,    9,      1]
[   9, None,    3, None,      1]
[None,    5,    4, None,      1]

[   8,    4,    3,    8,   None]

Answer 1

这个问题可以换个说法，把它看作一个线性方程组，然后用numpy.linalg.solve这个工具来解决。

import numpy as np
from copy import copy
from random import randint

matriz_aux = [
[None, 6, None, 9],
[9, None, 3, None],
[None, 5, 4, None],
]

matrix_aux_with_num_decompositions = copy(matriz_aux)

matriz_aux = np.array(matriz_aux)

rows, cols = matriz_aux.shape

seq = np.zeros((rows+cols, rows+cols))

vals = []

# Setup matrix representing system of equations
for i in range(rows):
    for j in range(cols):
        if matriz_aux[i,j]:
            seq[len(vals), i] = 1
            seq[len(vals), rows + j] = 1
            vals.append(matriz_aux[i,j])

# Set arbitrary values so matrix is non-singular
for extra_eq in range(len(vals), rows+cols):
    seq[extra_eq, extra_eq] = 1
    vals.append(randint(0, 100))

dcmp = np.linalg.solve(seq, vals)

for row in range(rows):
    matrix_aux_with_num_decompositions[row].append(dcmp[row])

matrix_aux_with_num_decompositions.append(list(dcmp[rows:]))