algorithm - pseint - permutacion de numeros en c++

Un algoritmo para detectar permutaciones de matrices Hankel (3)

Intento escribir código para detectar si una matriz es permutación de una matriz de Hankel, pero no puedo pensar en una solución eficiente que no sea la fuerza bruta muy lenta. Aquí está la especificación.

Entrada: Una n por n matriz M cuyas entradas son 1 o 0.

Formato de entrada: filas separadas por espacios. Una fila por línea Por ejemplo

0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1

Salida: Una permutación de las filas y columnas de M de modo que M es una matriz de Hankel si eso es posible. Una matriz de Hankel tiene diagonales sesgadas constantes (diagonales con pendiente positiva).

Cuando digo una permutación, quiero decir que podemos aplicar una permutación al orden de las filas y posiblemente una diferente a las columnas.

Estaría muy agradecido por cualquier idea.

Aquí hay algunas ideas.

1)

Las permutaciones de fila y columna conservan las sumas de fila y columna :

1 0 1 0 - 2 0 0 0 1 - 1 row sums 1 0 0 0 - 1 1 1 1 0 - 3 | | | | 3 1 2 1 column sums

Cualquiera que sea la forma en que permute las filas, las sumas de las filas seguirán siendo {2, 1, 1, 3} en alguna permutación; las sumas de las columnas no se modificarán. Y viceversa. Las matrices de Hankel y sus permutaciones siempre tendrán el mismo conjunto de sumas de fila que las sumas de columna. Esto le da una prueba rápida para descartar un conjunto de matrices no viables.

2)

Postulo que las matrices de Hankel siempre se pueden permutar de tal forma que sus sumas de fila y columna estén en orden ascendente , y el resultado sigue siendo una matriz de Hankel:

0 1 1 0 - 2 0 0 0 1 - 1 1 1 0 0 - 2 0 0 1 1 - 2 1 0 1 1 - 3 --> 0 1 1 0 - 2 0 0 1 0 - 1 1 1 0 1 - 3 | | | | | | | | 2 2 3 1 1 2 2 3

Por lo tanto, si una matriz se puede permutar en una matriz de Hankel, también se puede permutar en una matriz de Hankel de suma ascendente de fila y columna. Es decir, podemos reducir el número de permutaciones necesarias para probar al solo probar permutaciones donde las sumas de fila y columna están en orden ascendente.

3)

Además, postulo que para cualquier matriz de Hankel donde dos o más filas tienen la misma suma, cada permutación de columnas tiene una permutación correspondiente de filas que también produce una matriz de Hankel. Es decir, si existe una matriz de Hankel para una permutación de columnas, entonces existe para cada permutación de columnas, ya que podemos simplemente aplicar esa misma permutación a las filas correspondientes y lograr un resultado simétrico.

El resultado es que solo necesitamos probar permutaciones de filas o columnas, no filas y columnas.

Aplicado al ejemplo original:

1 0 1 0 - 2 0 0 0 1 0 1 0 0 - 1 0 0 0 1 0 0 0 1 - 1 1 0 0 0 0 0 0 1 - 1 0 1 0 0 1 0 0 0 - 1 --> 1 0 1 0 --> 0 0 1 1 - 2 --> 0 0 1 1 = Hankel! 1 1 1 0 - 3 1 1 1 0 1 0 1 1 - 3 1 0 1 1 | | | | 3 1 2 1 permute rows into| ditto | try swapping ascending order | for columns | top 2 rows

4)

Yo postulo, finalmente, que cada matriz de Hankel donde hay múltiples filas y columnas con la misma suma se puede permutar en otra matriz de Hankel con la propiedad de que esas filas y columnas están en orden creciente cuando se leen como números binarios , leyendo de izquierda a a la derecha para las filas y de arriba a abajo para las columnas. Es decir:

0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 New 1 0 1 0 --> 1 0 0 1 --> 1 0 1 0 Hankel 0 1 0 1 1 0 1 0 1 1 0 0 Original rows columns Hankel ascending ascending

Si esto es cierto (y aún estoy indeciso), entonces solo necesitamos crear y probar una permutación de cualquier matriz de entrada dada. Esa permutación coloca las filas y columnas en orden de suma ascendente, y en el caso de sumas iguales, las ordena por sus interpretaciones de números binarios. Si esta matriz resultante no es Hankel, entonces no hay permutación que lo haga Hankel.

¡Espero que te lleve a un algoritmo!

Addendum: Contraejemplos?

Probando el ejemplo de @ orlp:

0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 --> 0 1 1 1 --> 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 (A) (B) (C)

A: Original Hankel. Las sumas de fila son 1, 2, 3, 3; Las filas 3 y 4 no están en orden binario.
B: Intercambie las filas 3 y 4. Las columnas 3 y 4 no están en orden binario.
C: Intercambie las columnas 3 y 4. El resultado es Hankel y satisface todas las propiedades.

Probando el ejemplo de @Degustaf:

1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 --> 1 0 1 0 --> 1 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 (A) (B) (C)

A: matriz original de Hankel. Las sumas de fila son 3, 2, 1, 2.
B: Reorganice para que las sumas de fila sean 1, 2, 2, 3, y las filas de la suma 2 estén en orden binario ascendente (es decir, 1001, 1010)
C: Reordenar las sumas de columna a 1, 2, 2, 3, con las dos columnas de suma 2 en orden (0101, 1001). El resultado es Hankel y satisface todas las propiedades. Tenga en cuenta también que la permutación en las columnas coincide con la permutación en las filas: el nuevo orden de columnas del anterior es {3, 4, 2, 1}, la misma operación para obtener de A a B.

Nota: sugiero el orden binario (n. ° 4) solo para situaciones de desempate en la suma de fila o columna, no como un reemplazo para el ordenamiento (n. ° 2).

Sin pérdida de generalidad, supondremos que hay menos de 0 que de 1. Entonces podemos encontrar las posibles diagonales en una Matriz de Hankel que podrían ser 0 para darnos el número apropiado de 0 en toda la matriz. Y, esto nos dará las posibles matrices de Hankel. A partir de ahí, puede contar el número de 0 en cada columna y compararlo con el número de 0 en las columnas de la matriz original. Una vez que haya hecho esto, tiene un espacio mucho más pequeño para realizar una búsqueda de fuerza bruta: permutando en columnas y filas que tienen el número correcto de 0.

Ejemplo: OP sugirió una matriz 4x4 con 7 0''s. Necesitamos dividir esto utilizando el conjunto {4,3,3,2,2,1,1} . Entonces, o las particiones serían:

{4,3}
{4,2,1} (2 de estas matrices)
{3,3,1}
{3,2,2}
{3,2,1,1} (2 de estas matrices)

Y esto nos da las matrices de Hankel (sin incluir las simetrías)

1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0

La matriz original tenía columnas con 3, 1, 2 y 1 0 en sus cuatro columnas. Comparando esto con las 7 posibles matrices de Hankel nos da 2 posibilidades

1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0

Ahora, solo hay 4 posibles permutaciones que pueden asignar la matriz original a cada una de ellas: solo tenemos 1 opción basada en las columnas con 2 y 3 0, pero 2 opciones para las columnas con 1 0, y también 2 opciones para la filas con 1 0''s. Comprobando esas permutaciones, vemos que la siguiente matriz de Hankel es una permutación del original

0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0

La única cosa que la primera respuesta a esta pregunta es correcta es que permutando las filas y columnas no cambia las sumas de las filas o las sumas de las columnas.

Otra observación fácil es que en una matriz de Hankel, la diferencia en la suma de filas entre dos filas consecutivas es -1, 0 o 1, y cada caso nos da una restricción en las filas. Si la diferencia es 0, la variable de entrada es igual a la variable que sale; de lo contrario, sabemos cuál es 0 y cuál es 1.

0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1

tiene sumas de fila 3, 2, 1, 3. Las órdenes que respetan el requisito de diferencia son 1 2 3 3 y 3 3 2 1, y wlog podemos descartar reversiones porque al invertir las permutaciones de fila y columna solo gira la matriz 180 grados. Por lo tanto, reducimos a considerar cuatro matrices permutadas (dos posibles ordenamientos de los 3 en las sumas de las filas y dos en las sumas de las columnas):

0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1

En realidad, podríamos haber llevado el análisis más allá al observar que forzando a las filas iniciales a tener sumas 1 y 2, limitamos el orden de las columnas con la suma 3, ya que

0 0 1 0 0 0 1 1

no es una inicial válida dos filas de una matriz de Hankel. Si este tipo de razonamiento es fácil de implementar depende de su paradigma de programación.

Tenga en cuenta que en el peor de los casos este tipo de razonamiento todavía no deja un número polinomial de casos a través de la fuerza bruta.