El problema general
Dada una matriz, me gustaría permutar el orden de los valores en cada fila, para que todas las columnas de la matriz sumen el mismo valor.
Un ejemplo sencillo
Por ejemplo, dado:
0 0 2 6
0 0 6 18
0 0 10 30
0 0 14 42
0 0 18 54
0 0 22 66Una solución es:
0 0 2 6
0 18 6 0
30 0 10 0
42 0 14 0
0 54 18 0
0 0 22 66Observa que cada columna suma 72. Por supuesto, la solución no es única; se pueden permutar las propias columnas para obtener soluciones diferentes, como:
0 0 2 6
18 0 6 0
0 30 10 0
0 42 14 0
54 0 18 0
0 0 22 66El problema específico
Aquí estoy viendo un simple $30 \times 5$ matriz. La matriz se define así: el contenido de la fila $n$ es $[0, 0, 2f(n), 6f(n), 12f(n)+2]$ donde $f(n) = 4n^2+4n+1$ y $n = 0, 1, 2, ...,29$ .
Este es el aspecto de la matriz:
0 0 2 6 14
0 0 18 54 110
0 0 50 150 302
0 0 98 294 590
0 0 162 486 974
0 0 242 726 1454
0 0 338 1014 2030
0 0 450 1350 2702
0 0 578 1734 3470
0 0 722 2166 4334
0 0 882 2646 5294
0 0 1058 3174 6350
0 0 1250 3750 7502
0 0 1458 4374 8750
0 0 1682 5046 10094
0 0 1922 5766 11534
0 0 2178 6534 13070
0 0 2450 7350 14702
0 0 2738 8214 16430
0 0 3042 9126 18254
0 0 3362 10086 20174
0 0 3698 11094 22190
0 0 4050 12150 24302
0 0 4418 13254 26510
0 0 4802 14406 28814
0 0 5202 15606 31214
0 0 5618 16854 33710
0 0 6050 18150 36302
0 0 6498 19494 38990
0 0 6962 20886 41774Obviamente, la suma deseada para cada columna es igual a la suma de todos los elementos de la matriz dividida por el número de columnas. En este caso es $\frac{1}{5}\left(60 + 20\sum_{n=0}^{29} f(n)\right) = 143972$ .
Desde luego, no podemos hacerlo por la fuerza bruta: Para un $m\times n$ matriz el número de posibilidades son: $(n!)^m$ que explota combinatoriamente. Aquí, dos de las columnas dadas son ceros por lo que tenemos $\left(\frac{n!}{2}\right)^m$ formas únicas de permutar los valores de cada fila, lo que no es mucho mejor.
Afortunadamente, esta matriz tiene un patrón bien definido, y me pregunto: ¿se puede aprovechar este patrón para derivar soluciones más fácilmente?
EDIT : He realizado una búsqueda recursiva en profundidad para encontrar soluciones. En cada iteración, intenta construir un vector que sume el resultado deseado (en este caso 143972) eligiendo cada entrada del vector de una fila diferente de la matriz. Una vez que se ha creado un vector de este tipo, se eliminan las entradas elegidas de la matriz, pasando así de ser un $m\times n$ matriz a una $m \times n-1$ uno. Esto se repite hasta que no se encuentra ninguna solución o hasta que la matriz se vacía. En el peor de los casos, se ejecuta del orden de $n^m$ para un $m\times n$ matriz (pero resulta que encontrar una solución es rápido porque mi matriz tiene muchas, muchas soluciones aparentemente).
Aquí hay tres ejemplos de soluciones que he encontrado utilizando este enfoque:
Solución 1
6 14 0 0 2
0 54 18 110 0
50 0 0 302 150
0 0 98 590 294
0 0 162 486 974
0 0 242 1454 726
338 0 1014 0 2030
0 450 0 2702 1350
0 0 578 1734 3470
0 0 722 2166 4334
0 0 882 2646 5294
0 0 1058 3174 6350
0 0 1250 3750 7502
0 0 1458 4374 8750
0 0 1682 5046 10094
0 0 1922 11534 5766
0 2178 0 6534 13070
0 0 2450 7350 14702
0 0 2738 16430 8214
0 0 3042 18254 9126
3362 0 20174 10086 0
0 3698 22190 11094 0
0 12150 24302 4050 0
0 26510 13254 4418 0
0 28814 14406 4802 0
31214 15606 5202 0 0
33710 16854 5618 0 0
36302 18150 6050 0 0
38990 19494 6498 0 0
0 0 6962 20886 41774Solución 2
6 0 2 0 14
0 110 0 54 18
0 150 0 50 302
294 590 0 0 98
486 974 0 162 0
726 242 1454 0 0
1014 2030 0 338 0
2702 450 1350 0 0
1734 3470 578 0 0
4334 2166 722 0 0
5294 2646 882 0 0
3174 6350 1058 0 0
7502 3750 1250 0 0
8750 4374 0 1458 0
10094 5046 1682 0 0
11534 5766 1922 0 0
13070 6534 2178 0 0
14702 7350 2450 0 0
16430 8214 2738 0 0
18254 9126 3042 0 0
20174 10086 3362 0 0
3698 22190 11094 0 0
0 24302 12150 4050 0
0 13254 26510 0 4418
0 4802 28814 14406 0
0 0 15606 31214 5202
0 0 5618 33710 16854
0 0 6050 18150 36302
0 0 6498 19494 38990
0 0 6962 20886 41774Solución 3
0 14 0 6 2
0 18 110 0 54
0 0 302 150 50
0 590 294 98 0
162 974 0 486 0
1454 242 726 0 0
0 1014 2030 338 0
450 1350 2702 0 0
0 1734 3470 0 578
722 4334 2166 0 0
0 2646 5294 882 0
1058 3174 6350 0 0
0 3750 7502 1250 0
1458 4374 8750 0 0
0 5046 10094 1682 0
5766 11534 1922 0 0
2178 0 13070 6534 0
7350 14702 2450 0 0
0 2738 8214 16430 0
18254 9126 3042 0 0
0 3362 10086 20174 0
11094 22190 3698 0 0
0 4050 12150 24302 0
26510 13254 4418 0 0
0 0 4802 14406 28814
31214 15606 5202 0 0
0 0 5618 16854 33710
36302 18150 6050 0 0
0 0 6498 19494 38990
0 0 6962 20886 41774Pero todavía no sé si hay una manera de contar el número de soluciones, o cómo generar más soluciones de forma más eficiente. Y mi algoritmo de búsqueda en profundidad es una forma más bien de fuerza bruta que no aprovecha la secuencia conocida de la que se compone la matriz original.
