arrays - que - Cómo construir una matriz binaria a partir de sumas

matrices en matlab programacion

Question

Tengo dos variables de número decimal, colSum y rowSum, usando aquellas para las que quiero construir una matriz de valores binarios basados ​​en esas sumas, la variable de matriz rowSum es el resultado de agregar todos los 1 para cada fila, lo mismo para colSum array.

Entonces, si tienes

rowSum = [0,1,2]
colSum = [1,1,1]

deberás construir correctamente la siguiente matriz

matrix = [
 [0,0,0],
 [0,0,1],
 [1,1,0]
]

Estoy usando este método en PHP, que funciona para una matriz de 3x3, pero no para una más grande, como 8x8. Primero, complete todos los 1 en las filas usando el valor de rowSum. Luego, trate de encontrar un valor de suma incorrecto de 2 columnas, con un pivote las cambio (1 con un valor cero) en la misma fila, hasta que obtenga el valor correcto de colSum. Pero no funcionará porque necesito cierto control de los criterios para cambiar el 1 y el 0 en la misma fila para dos columnas ...

Este es el método que estoy usando.

Digamos que tenemos esta Matriz (N = 3 -> NxN):

0  0  0
0  0  1
1  1  0

entonces tenemos las siguientes matrices

R0 = {0,1,2} //--> result of sums of each rows: ( 0+0+0, 0+0+1 , 1+1+0 )
C0 = {1,1,1} // ->sums of each columns

Paso 1

Crea y completa una matriz NxN usando tantos 1 como R0 (i) en cada fila:

0  0  0
1  0  0
1  1  0 

calcular las sumas de esta nueva matriz ahora: R1 = {0,1,2} C1 = {2,1,0}

Paso 2

Compruebe si para todos los elementos de la columna, las sumas de la matriz creada tienen el mismo valor que C0 (origen)

for ( i=0, N-1) do

 if C0(i)!=C1(i) then
   ReplaceColumn(i)
 end

end

Para reemplazar una columna tenemos que cavar dentro de las condiciones. C0 (0) = 1! = C1 (0) = 2 la suma de la primera columna cumple la condición para llamar al reemplazo, por lo tanto

Paso 3

Elija los criterios para aplicar el método de bifurcación y enlace y encuentre la mejor fila para cambiar la columna que satisfaga la condición global (todas las sumas de columna).

La cantidad de cambios para una diferencia entre sumas de columnas es:

|C0(i)-C1(i)| 

para este ejemplo, | C0 (0) -C1 (0) | = 1 cambio La condición de devolución debe ser si el cambio genera una mayor diferencia entre la suma total de columnas.

Σi,N(|C0(i)-C1(i)|)

Entonces, ¿podría funcionar realmente este método?

Answer 1

¿El objetivo es construir la matriz que satisfaga las sumas de fila y columna o una matriz que las satisfaga? No está claro a partir de la pregunta, pero si es el primero (" el " caso), entonces no será posible.

Supongamos que fuera el caso que pudieras representar de manera única cualquier matriz de bits m × m de esta manera. Luego considere el siguiente algoritmo hipotético de compresión.

• Toma 2 ²ⁿ bits de datos
• Trátelo como 2 ⁿ × 2 ⁿ bits
• Para describir los datos, use sumas de 2 × 2 ⁿ filas y columnas, cada una usando como máximo log ₂ (2 ⁿ ) = n bits
• Los datos se comprimen a 2 × n × 2 ⁿ bits

Dado que 2 × n × 2 ⁿ << 2 ²ⁿ y este proceso podría seguir repitiéndose, la suposición de que se puede representar de manera única cualquier matriz de bits m × m solo por sus sumas de fila y columna es falsa.