Reordenar las columnas y filas de una matriz de forma que se pueda dividir por la mitad

Question

No soy matemático, así que disculpen si esta pregunta resulta ser trivial. Necesito esto en el trabajo, pero no pude averiguar cómo resolver esto de manera eficiente, aunque parece que podría ser un problema muy común, y tal vez simple (sin embargo tengo un mal presentimiento sobre esto).

En cualquier caso, dada es una matriz de valores booleanos, es decir, ceros y unos.

Las operaciones permitidas son:

1. Las filas se pueden intercambiar
2. Las columnas se pueden intercambiar

El problema: utilizando sólo estas dos operaciones, ¿es posible convertir la matriz de entrada en una especie de matriz diagonal de bloques, con la salvedad de que los bloques no deben ser necesariamente matrices cuadradas, sino de tamaño restringido, es decir, el número de filas (o columnas) de cada bloque debe ser igual a un número determinado.

Por ejemplo:

Sea la matriz de entrada:

    a b c d e f
--+------------
w | 1 0 0 0 1 0
x | 0 0 0 1 0 1
y | 1 0 1 0 0 0
z | 0 1 0 1 0 0

Y los bloques deben tener el tamaño (2,3), entonces una posible solución sería:

    a e c d b f
--+------------
w | 1 1 0 0 0 0
y | 1 0 1 0 0 0
x | 0 0 0 1 0 1
z | 0 0 0 1 1 0

Aquí se han intercambiado las filas x e y las columnas b y e.

El problema también puede relajarse de forma que sólo se fije el número de columnas (o filas, pero no ambos) de las submatrices.

Lo necesito para encajar una matriz bastante grande pero escasa en una hoja de papel de anchura limitada, y la idea era reorganizarla como se ha descrito anteriormente y dividirla por la mitad. Sé que no siempre es posible, pero en los casos en que sí lo es, procedería a mostrar la matriz resultante así:

    a e c
--+------
w | 1 1 0
y | 1 0 1

    d b f
--+------
x | 1 0 1
z | 1 1 0

Así que mi pregunta es: ¿cómo se llama generalmente este problema? ¿Existe una formulación alternativa? Y, lo que es más importante, ¿existe un algoritmo (eficiente) para resolverlo (es decir, debe haber uno, no)? ¿Hay algún texto o algo en la web donde pueda buscarlo?

Muchas gracias por adelantado.

ACTUALIZACIÓN

He avanzado un poco en esto y -si no me he equivocado- resulta que se reduce a PARTICIÓN.

Básicamente, es relativamente fácil agrupar columnas en clases de equivalencia comprobando si hay alguna fila que tenga 1s en ambas columnas. Se me ocurrió este algoritmo:

1. elige alguna celda con un 1
2. golpear a través de él verticalmente y horizontalmente
3. para cada celda que contenga un 1 que sea tachado, realice los pasos 2-3.
4. eliminar la submatriz que contiene filas y columnas tachadas y repetir los pasos 1-4 hasta que no queden 1s

De este modo, obtenemos el conjunto de submatrices más pequeñas que luego deben combinarse para formar dos matrices de igual anchura (el objetivo era dividir la matriz de entrada por la mitad). En realidad, en el caso de que haya columnas todo-0, éstas pueden usarse para rellenar otras matrices hasta el tamaño requerido, pero esto sólo complica las cosas.

Además, en la segunda fase (combinar las submatrices), sólo es relevante la anchura de las submatrices, por lo que podemos considerar un conjunto múltiple de enteros positivos que representen la anchura de cada submatriz.

Exigir que este conjunto sea particionado en dos subconjuntos que sumen igual tamaño, bueno, eso es exactamente PARTICIONAR (sabía que había algo malo en este problema _).

Por cierto, dividir la matriz en más de dos trozos de tamaño más o menos igual se reduce a BIN PACKING.

Answer 1

Básicamente se trata de grafos bipartitos: grafos en los que el conjunto de vértices se divide en dos partes que llamaré tipo $X$ vértices y tipo $Y$ vértices, y donde todas las aristas tienen un extremo de tipo $X$ y otro del tipo $Y$ . T $X$ y $Y$ la relación que se mantiene entre $x$ y $y$ si hay una arista entre $x$ y $y$ . En su ejemplo escriba $X$ los elementos serían los índices de las filas y el tipo $Y$ serían índices de columna (por lo que un número que es a la vez un índice de fila y un índice de columna da lugar a un tipo $X$ vértice y un tipo no relacionado $Y$ vértice), y las aristas del grafo son entre pares $(x,y)$ donde la matriz tiene una entrada no nula en la posición $(x,y)$ . Permutar las filas y las columnas ahora sólo significa renumerar el tipo $X$ respectivamente el tipo $Y$ vértices, por lo que se puede pensar que estos conjuntos no están etiquetados, lo que ayuda a abstraerse del orden en que se dan inicialmente las filas y las columnas.

Ahora lo que se quiere es dividir todo el grafo en trozos de tal manera que no haya aristas entre diferentes trozos (y además se quiere que cada trozo tenga números específicos de tipo $X$ y escriba $Y$ vértices). La partición más fina con esta propiedad se obtiene calculando el componentes conectados de tu gráfico bipartito. Existe un algoritmo sencillo y eficiente para calcular las componentes conectadas. Incluso en el caso de los grafos dispersos, es muy posible que sólo haya una componente conectada, en cuyo caso no hay suerte. Sin embargo, suponiendo que haya muchas componentes conectadas, la siguiente tarea es agrupar las componentes conectadas en trozos para que el número de tipos $X$ y escriba $Y$ vértices coincide con su especificación para cada trozo. Se trata de un tipo de problema de empaquetado de cubos, pero con la particularidad de que los tamaños de los elementos que hay que empaquetar son pares de números en lugar de números simples (es decir, los números de tipo $X$ y escriba $Y$ vértices), cuyos tamaños se suman como $2$ -vectores componentes.

No parece un problema fácil, ni en lo que respecta a la probabilidad de que exista una solución, ni en lo que respecta a permitir algoritmos eficientes para resolver el caso general resoluble. Personalmente, me sentiría algo desmotivado para dedicar mucho esfuerzo a este problema.