Having this matrix I want to decompose the numerical values (those that are not None), in this case 6, 9, 9, 3, 5, and 4 into 2 numbers that added together give those numbers.
matrix_aux = [
[None, 6, None, 9],
[ 9, None, 3, None],
[None, 5, 4, None]
]
A combination should be left by placing an additional column in the matrix matrix_aux, and then an additional row, in which a decomposition of the numerical values that were in the original matrix_aux will be made.
A decomposition like this should follow, ensuring that all decompositions respect those already carried out previously. This would be a correct output:
matrix_aux_with_num_decompositions = [
[None, 6, None, 9, 4],
[ 9, None, 3, None, 2],
[None, 5, 4, None, 3],
[ 7, 2, 1, 5 ]
]
Note that all decompositions respect each other mutually,
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
To solve this problem, I think you should use a combination of techniques, including backtracking and dynamically updating the array.
# 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)
I have tried this code but it gives me decompositions that contradict each other, for example here it is saying that 3 = 3 + 1, which does not make sense
[None, 6, None, 9, 1]
[ 9, None, 3, None, 1]
[None, 5, 4, None, 1]
[ 8, 4, 3, 8, None]
This problem can be re-phrased as a linear system of equations and then solved with 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:]))