¿Cómo se hacen las conversiones de matriz por filas y columnas?

Question

Tengo una matriz cuadrada que consta de elementos 1 o 0. Un alternador de fila alterna todos los elementos de la fila ith (1 se convierte en 0 y viceversa) y la alternancia de la columna j alterna todos los elementos de la columna jth . Tengo otra matriz cuadrada de tamaño similar. Deseo cambiar la matriz inicial a la matriz final usando la cantidad mínima de conmutadores. Por ejemplo

|0 0 1| 
|1 1 1| 
|1 0 1| 

a

|1 1 1| 
|1 1 0| 
|1 0 0| 

requeriría un conmutador de la primera fila y la última columna de la .

¿Cuál será el algoritmo correcto para esto?

Answer 1

En general, el problema no tendrá solución. Para ver esto, nótese que transformar la matriz A en la matriz B es equivalente a transformar la matriz A - B (calculada usando aritmética binaria, de modo que 0 - 1 = 1) en la matriz cero. Mire la matriz A - B y aplique la columna alterna (si es necesario) para que la primera fila se convierta en 0 o en 1. En este punto, ya ha terminado con las columnas que se alternan: si alternar una columna, debe alternarlas todas para que la primera fila sea correcta. Si incluso una fila es una mezcla de 0 y 1 en este punto, el problema no se puede resolver. Si cada fila ahora es todo 0 o todo 1, el problema se puede resolver al alternar las filas apropiadas para llegar a la matriz cero.

Para obtener el mínimo, compare el número de conmutadores necesarios cuando la primera fila se convierte en 0 contra 1. En el ejemplo de OP, los candidatos cambiarían la columna 3 y la fila 1 o alternarían las columnas 1 y 2 y las filas 2 y 3. De hecho, puede simplificar esto al observar la primera solución y ver si el número de conmutadores es más pequeño o mayor que N - si es mayor que N, que alternar las filas y columnas opuestas.

Answer 2

Si solo puede alternar las filas, y no las columnas, solo habrá un subconjunto de matrices que puede convertir en el resultado final. Si este es el caso, entonces sería muy simple:

for every row, i: 
    if matrix1[i] == matrix2[i] 
    continue; 
    else 
    toggle matrix1[i]; 
    if matrix1[i] == matrix2[i] 
     continue 
    else 
     die("cannot make similar"); 

Answer 3

No siempre es posible. Si comienza con una matriz de 2x2 con un número par de 1s, nunca podrá llegar a una matriz final con un número impar de 1s.

Answer 4

Se me ocurrió un algoritmo de fuerza bruta.

El algoritmo se basa en conjeturas 2:
^{(por lo que puede no funcionar para todas las matrices - Voy a verificar más tarde)}

• El mínimo (número de palancas acodadas) solución contendrá una específica fila o columna solo una vez.
• En cualquier orden que apliquemos los pasos para convertir la matriz, obtenemos el mismo resultado.

El algoritmo:
digamos que tenemos la matriz m = [[1,0], [0,1]].

m: 1 0 
    0 1 

Generamos una lista de todos los números de fila y columna,
así: ['r0', 'r1', 'c0', 'c1']

Ahora que la fuerza bruta, también conocido como examinar, cada posibles combinaciones de pasos.
Por ejemplo,
empezamos con una solución de 1-paso,
ksubsets = [['r0'], ['r1'], ['c0'], ['c1']]

si ningún elemento es una solución luego proceder con una solución de 2 pasos,
ksubsets = [['r0', 'r1'], ['r0', 'c0'], ['r0', 'c1'], ['r1', 'c0'], ['r1', 'c1'], ['c0', 'c1']]

etc ...

Un El elemento ksubsets (combo) es una lista de pasos de alternar para aplicar en una matriz.

---

implementación de Python (probado en la versión 2.5)

# Recursive definition (+ is the join of sets) 
# S = {a1, a2, a3, ..., aN} 
# 
# ksubsets(S, k) = { 
# {{a1}+ksubsets({a2,...,aN}, k-1)} + 
# {{a2}+ksubsets({a3,...,aN}, k-1)} + 
# {{a3}+ksubsets({a4,...,aN}, k-1)} + 
# ... } 
# example: ksubsets([1,2,3], 2) = [[1, 2], [1, 3], [2, 3]] 
def ksubsets(s, k): 
    if k == 1: return [[e] for e in s] 
    ksubs = [] 
    ss = s[:] 
    for e in s: 
     if len(ss) < k: break 
     ss.remove(e) 
     for x in ksubsets(ss,k-1): 
      l = [e] 
      l.extend(x) 
      ksubs.append(l) 
    return ksubs 

def toggle_row(m, r): 
    for i in range(len(m[r])): 
     m[r][i] = m[r][i]^1 

def toggle_col(m, i): 
    for row in m: 
     row[i] = row[i]^1 

def toggle_matrix(m, combos): 
    # example of combos, ['r0', 'r1', 'c3', 'c4'] 
    # 'r0' toggle row 0, 'c3' toggle column 3, etc. 
    import copy 
    k = copy.deepcopy(m) 
    for combo in combos: 
     if combo[0] == 'r': 
      toggle_row(k, int(combo[1:])) 
     else: 
      toggle_col(k, int(combo[1:])) 

    return k 

def conversion_steps(sM, tM): 
# Brute force algorithm. 
# Returns the minimum list of steps to convert sM into tM. 

    rows = len(sM) 
    cols = len(sM[0]) 
    combos = ['r'+str(i) for i in range(rows)] + \ 
      ['c'+str(i) for i in range(cols)] 

    for n in range(0, rows + cols -1): 
     for combo in ksubsets(combos, n +1): 
      if toggle_matrix(sM, combo) == tM: 
       return combo 
    return [] 

Ejemplo:

m: 0 0 0 
    0 0 0 
    0 0 0 

k: 1 1 0 
    1 1 0 
    0 0 1 

>>> m = [[0,0,0],[0,0,0],[0,0,0]] 
>>> k = [[1,1,0],[1,1,0],[0,0,1]] 
>>> conversion_steps(m, k) 
['r0', 'r1', 'c2'] 
>>> 

Answer 5

Este es un problema de búsqueda de espacio de estado. Está buscando la ruta óptima desde un estado inicial hasta un estado de destino. En este caso particular, "óptimo" se define como "número mínimo de operaciones".

El espacio de estados es el conjunto de matrices binarias generables desde la posición de inicio mediante operaciones de alternancia de filas y columnas.

ASUMIENDO que el destino se encuentra en el espacio de estado (NO es una suposición válida en algunos casos: ver la respuesta de Henrik), intentaría realizar una búsqueda heurística clásica (probablemente A *, ya que se trata de lo mejor de la raza) algoritmo en el problema y ver qué sucedió.

La primera y más obvia heurística es "número de elementos correctos".

Cualquier libro de texto decente de Inteligencia Artificial discutirá la búsqueda y el algoritmo A *.

Puede representar su matriz como un entero no negativo, con cada celda en la matriz correspondiente exactamente a un bit en el entero En un sistema que admite 64 bits largos sin signo, esto le permite jugar con cualquier objeto hasta 8x8 . A continuación, puede usar operaciones O exclusivas en el número para implementar las operaciones de alternar filas y columnas.

PRECAUCIÓN: el tamaño del espacio de estado total sin procesar es 2^(N^2), donde N es el número de filas (o columnas). Para una matriz 4x4, son 2^16 = 65536 estados posibles.

Answer 6

Algoritmo

simplificar el problema de "intentar transformar A en B" en "Tratar de transformar M en 0", donde M = A XOR B. Ahora todas las posiciones que deben ser activadas o tienen una 1 en ellos.

Considere una posición arbitraria en M. Se ve afectada exactamente por una columna alternar y exactamente una fila alternar. Si su valor inicial es V, la presencia del alternar de columna es C, y la presencia del alternar de fila es R, entonces el valor final F es V xo C xor R. Esa es una relación muy simple, y hace que el problema sea trivial resolver.

Observe que, para cada posición, R = F xor V xo C = 0 xor V xo C = V xo C. Si configuramos C, forzamos el valor de R, y viceversa. Eso es increíble, porque significa que si configuro el valor de cualquier alternancia de fila, forzaré todos los de la columna. Cualquiera de esos conmutadores de columna forzará todos de la fila alterna. Si el resultado es la matriz 0, entonces tenemos una solución. ¡Solo tenemos que probar dos casos!

Pseudo-código

function solve(Matrix M) as bool possible, bool[] rowToggles, bool[] colToggles: 
    For var b in {true, false} 
     colToggles = array from c in M.colRange select b xor Matrix(0, c) 
     rowToggles = array from r in M.rowRange select colToggles[0] xor M(r, 0) 
     if none from c in M.colRange, r in M.rowRange 
       where colToggle[c] xor rowToggle[r] xor M(r, c) != 0 then 
      return true, rowToggles, colToggles 
     end if 
    next var 
    return false, null, null 
end function 

Análisis

El análisis es trivial. Intentamos dos casos, dentro de los cuales corremos a lo largo de una fila, luego una columna y luego todas las celdas. Por lo tanto, si hay r filas yc columnas, lo que significa que la matriz tiene tamaño n = c * r, entonces la complejidad del tiempo es O (2 * (c + r + c * r)) = O (c * r) = O (norte). El único espacio que usamos es lo que se requiere para almacenar las salidas = O (c + r).

Por lo tanto, el algoritmo toma tiempo lineal en el tamaño de la matriz, y utiliza el espacio lineal en el tamaño de la salida. Es asintóticamente óptimo por razones obvias.

Answer 7

En lugar de considerar esto como un problema de matriz, tome los 9 bits de cada matriz, cargue cada uno de ellos en tipos de tamaño de 2 bytes (16 bits, que es probablemente la fuente de las matrices en primer lugar), luego haz un solo XOR entre los dos.

(el orden de los bits sería diferente dependiendo de su tipo de CPU)

La primera matriz se convertiría en: 0000000001111101 la segunda matriz se convertiría en: 0000000111110101

Un único XOR produciría la salida. No se requieren bucles Todo lo que tendrías que hacer es 'descomprimir' el resultado en una matriz, si aún así lo deseas. Sin embargo, puede leer los bits sin recurrir a eso.

Answer 8

Creo que la fuerza bruta no es necesaria.

El problema se puede reformular en términos de un grupo. Las matrices sobre el campo con 2 elementos constituyen un grupo conmutativo con respecto a la suma.

Como se señaló anteriormente, la pregunta de si A puede cambiarse a B es equivalente a ver si AB puede alternarse en 0. Tenga en cuenta que al alternar la fila i se realiza agregando una matriz con solo en la fila iy De lo contrario, ceros, mientras que al alternar la columna j se hace agregando una matriz con solo los de la columna j y ceros en caso contrario.

Esto significa que A-B puede alternar a la matriz cero si y solo si A-B está contenido en el subgrupo generado por las matrices de alternancia.

Como la adición es conmutativa, primero se realiza el alternar de las columnas y podemos aplicar el enfoque de Marius primero a las columnas y luego a las filas.

En particular, al alternar las columnas debe hacer que cualquier fila sea uno o todos los ceros. hay dos posibilidades:

1. Alternar las columnas de modo que cada 1 en la primera fila se vuelva cero.Si después de esto hay una fila en la que ocurren los unos y los ceros, no hay solución. De lo contrario, aplique el mismo enfoque para las filas (ver a continuación).

2. Alternar las columnas de modo que cada 0 en la primera fila se convierta en 1. Si después de esto hay una fila en la que se producen tanto unos como ceros, no hay solución. De lo contrario, aplique el mismo enfoque para las filas (ver a continuación).

Dado que las columnas se han alternado con éxito en el sentido de que en cada fila contiene sólo unos o ceros, hay dos posibilidades:

1. filas de palanca de tal manera que cada 1 en la primera columna se convierte cero.

2. Alterne las filas de manera que cada 0 en la primera fila pase a ser cero.

Por supuesto, en el paso por las filas, tomamos la posibilidad que se traduce en menos alterna, es decir, contamos con los de la primera columna y luego decidir cómo alternar.

En total, solo se deben considerar 2 casos, es decir, cómo se alternan las columnas; para el paso de fila, el alternar puede decidirse contando para minimizar el número de conmutadores en el segundo paso.