Encuentre las filas que hacen que cada columna tenga un Verdadero (era: Algoritmo de Knuth X)

8

Tarea

Dada una matriz booleana, encuentre uno (u opcionalmente más) subconjunto (s) de filas que tienen exactamente un Verdadero en cada columna. Puede usar cualquier algoritmo , pero debe admitir matrices muy grandes, como el último ejemplo.

Un algoritmo posible ( Algoritmo X de Knuth )

Si bien no es necesario usar este algoritmo, puede ser su mejor opción.

  1. Si la matriz A no tiene columnas, la solución parcial actual es una solución válida; terminar con éxito
  2. De lo contrario, elija una columna c .
  3. Elija * una fila r tal que A r , c = 1.
  4. Incluya la fila r en la solución parcial.
  5. Para cada columna j de tal manera que A r , j = 1,
     para cada fila i tal que A i , j = 1,
      Borrar hilera i de la matriz A .
     eliminar la columna j de la matriz A .
  6. Repita este algoritmo de forma recursiva en la matriz reducida A .

* El paso 3 no es determinista, y debe retroceder en el caso de que no se encuentre una fila en una invocación posterior del paso 3.

Entrada

Cualquier representación deseada de la matriz A mínima de 2 × 2 , por ejemplo, como una matriz numérica o booleana

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

o como Universe + Set collection

U = {1, 2, 3, 4, 5, 6, 7}
S = {
    A = [1, 4, 7],
    B = [1, 4],
    C = [4, 5, 7],
    D = [3, 5, 6],
    E = [2, 3, 6, 7],
    F = [2, 7]
    }

o como 0 o 1 conjuntos indexados; {{1, 4, 7}, {1, 4}, {4, 5, 7}, {3, 5, 6}, {2, 3, 6, 7}, {2, 7}}.

Salida

Cualquier representación deseada de una (u opcionalmente más / todas) de las soluciones, por ejemplo, como una matriz numérica o booleana de las filas seleccionadas

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

o como una lista booleana que indica las filas seleccionadas {0, 1, 0, 1, 0, 1}o como una lista numérica (0 o 1 indexada) de las filas seleccionadas {2, 4, 6}o como una lista de nombres de conjuntos ['B', 'D', 'F'].

Más ejemplos

En:

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

Fuera: 1 3 o 4o 1 0 1 0o 0 0 0 1o [[1,3],[4]etc.


En:

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

Fuera: 1 1 0 0 etc.


En:

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

Fuera: 0 0 0 1 1 etc.


En:

0 1 1
1 1 0

Fuera: nada, error o solución defectuosa, es decir, no tiene que manejar entradas sin solución.


En: http://pastebin.com/raw/3GAup0fr

Fuera: 0 10 18 28 32 38 48 61 62 63 68 86 90 97 103 114 120 136 148 157 162 174 177 185 186 194 209 210 218 221 228 243 252 255 263 270 271 272 273 280 291 294 295 309 310 320 323 327 339 345 350 353 355 367 372 373 375 377 382 385 386 389 397 411 417 418 431 433 441 451 457 458 459 466 473 479 488 491 498 514 517


En: https://gist.github.com/angs/e24ac11a7d7c63d267a2279d416bc694

Fuera: 553 2162 2710 5460 7027 9534 10901 12281 12855 13590 14489 16883 19026 19592 19834 22578 25565 27230 28356 29148 29708 30818 31044 34016 34604 36806 36918 39178 43329 43562 45246 46307 47128 47906 48792 50615 51709 53911 55523 57423 59915 61293 62087 62956 64322 65094 65419 68076 70212 70845 71384 74615 76508 78688 79469 80067 81954 82255 84412 85227

Adán
fuente
44
" Solo las soluciones que usan este algoritmo son elegibles para ganar ", pero ¿qué cuenta exactamente como " este algoritmo "? ¿Cómo es literalmente necesario tomar " eliminar fila " y " eliminar columna "? ¿Y el algoritmo tiene que usar la heurística, que es una parte clave de la presentación del algoritmo de Knuth pero que no se menciona en absoluto en su descripción?
Peter Taylor
66
Puede ser mejor hacer una pregunta que solo solicite la cobertura exacta del conjunto, pero que tenga algunos casos de prueba fuertes que no pueden ser manejados por la fuerza bruta ingenua, pero sí pueden ser manejados por el algoritmo de Knuth.
Peter Taylor
1
Todos los algoritmos ahora están igualmente permitidos.
Adám
1
"debe admitir matrices muy grandes" es bastante ambiguo, especialmente porque el algoritmo de Knuth no puede manejar el caso de prueba grande sin la heurística de selección de columna. ¿Quizás tenga esta pregunta como código puro de golf y tenga otra como código más rápido ?
Angs

Respuestas:

5

Haskell, 100 93 92 87 83 80 bytes

Algoritmo de Knuth:

g&c=filter(g.any(`elem`c))
(u:v)%a=[c:s|c<-id&u$a,s<-(not&c)v%(not&c$a)]
x%_=[x]

Calcula todas las cubiertas de manera no determinante en profundidad en la mónada de la lista. Use headpara calcular solo uno ya que Haskell es vago. Uso:

*Main> [[1],[2],[3],[4],[5],[6],[7]]%[[1, 4, 7], [1, 4], [4, 5, 7], [3, 5, 6], [2, 3, 6, 7], [2, 7]]
[[[1,4],[2,7],[3,5,6]]]

Para obtener más velocidad utilizando la sugerencia de Knuth de seleccionar una columna con menos, use esto: (115 bytes, lista plana para universo). Encuentra la primera solución al gran problema de la cubierta de pentomino en menos de un minuto cuando se compila.

import Data.List
[]%_=[[]]
w%a=[c:s|c<-a,c\\(head.sortOn length.group.sort$w:a>>=id)/=c,s<-(w\\c)%[b|b<-a,c\\b==c]]

¡Gracias a @Zgarb por guardar 1 + 3 bytes!

Gracias a @ChristianSievers por sus sabios consejos y por ahorrar 5 bytes y algo más.

Sin golf (con universo de lista plana):

knuthX [] _ = [[]]
knuthX (u:niverse) availableRows = --u chosen deterministically
  [ chosen:solution
  | let rows = filter (elem u) availableRows
  , chosen <- rows  --row chosen nondeterministically in list monad
  , solution <- knuthX
                  (filter (not.(`elem`chosen)) niverse)
                  (filter (not.any(`elem`chosen)) availableRows)
  ]
Angs
fuente
Podría valer la pena agregar alguna explicación sobre cómo funciona para personas que no están familiarizadas con Haskell. ¿Estás usando la lista mónada para manejar el no determinismo, creo?
Puede guardar 3 bytes cambiando la filtercomprensión de una lista y definiendo una función auxiliar h!x=h(`elem`(x>>=id)).
Zgarb
1
@ChristianSievers Me encuentro con la restricción de monomorfismo con (!)=elem, por lo tanto, el a's. Y sí, definitivamente se puede usar f allí. ¡Gracias! Las diferentes combinaciones de filter … elemrogar se unifiquen ...
Angs
1
Podemos volver al universo plano, usar la versión que generalmente debería ser más rápida, pero no hace ninguna diferencia en el gran ejemplo, y guardar algunos bytes al usarlos w%a=[c:s|(u:_)<-[sortOn length.group.sort$w++concat a],c<-id&u$a,s<-(w\\c)%(not&c$a)]. Tenga en cuenta que ahora ues una lista que puede contener la columna elegida repetidamente, pero eso no importa para la corrección.
Christian Sievers
1
@ChristianSievers hurra, menos de + 50% de longitud de lento a rápido! Hubo una ligera regresión en la velocidad cuando uestaba en línea, ya que se calcula una vez por elemento a, pero apuntamos a la velocidad de golf, no a la velocidad óptima. c\\b==cprobablemente no sea tan malo ya que puede detenerse perezosamente. No alinear uy usar Data.Map.Strictpara encontrar el elemento más raro estaría en un nivel totalmente diferente.
Angs
1

Python, 482 bytes

r=lambda X,Y:u({j:set(filter(lambda i:j in Y[i],Y))for j in X},Y)
def u(X,Y,S=[]):
 if X:
  for r in list(X[min(X,key=lambda c:len(X[c]))]):
   S.append(r);C=v(X,Y,r)
   for s in u(X,Y,S):yield s
   w(X,Y,r,C);S.pop()
 else:yield list(S)
def v(X,Y,r):
 C=[]
 for j in Y[r]:
  for i in X[j]:
   for k in Y[i]:
    if k!=j:X[k].remove(i)
  C.append(X.pop(j))
 return C
def w(X,Y,r,C):
 for j in reversed(Y[r]):
  X[j]=C.pop()
  for i in X[j]:
   for k in Y[i]:
    if k!=j:X[k].add(i)

r es la función para llamar con la colección Universe + Set.

Golfé un poco desde esta página

Uso:

X = {1, 2, 3, 4, 5, 6, 7}
Y = {
    'A': [1, 4, 7],
    'B': [1, 4],
    'C': [4, 5, 7],
    'D': [3, 5, 6],
    'E': [2, 3, 6, 7],
    'F': [2, 7]}

for a in r(X,Y): print a
Karl Napf
fuente
Debería poder eliminar el yeso listen el primer bucle for y el rendimiento, y cambiar reversed(...)a...[::-1]
Azul
Cada vez que usa S.append(x)puede hacer S+=x,(con la coma final): por ejemplo C+=X.pop(j),.
FlipTack
1

R, 124 117 115 113 bytes

Muy ineficiente, pero no tanto en código. Intenta todos los subconjuntos posibles de filas y comprueba si todas las filas suman 1.

f=function(x,n=nrow(x))for(i in 1:n)for(j in 1:ncol(z<-combn(n,i)))if(all(colSums(x[k<-z[,j],,drop=F])==1))cat(k)

Toma una matriz como entrada. Devuelve los números de rown de la primera solución encontrada. No devuelve nada si no hay soluciones, pero puede demorar mucho tiempo si la entrada es grande.

Sin golf:

f=function(x, n=nrow(x)){


    for(i in 1:n){
        z=combn(n,i)

        for(j in 1:ncol(z)){
            k=x[z[,j],,drop=F]

            if(all(colSums(k)==1)){
                print(z[,j])
            }
        }
    }
}

7 bytes guardados gracias a Billywob

Otros 2 bytes guardados gracias a Billywob

JAD
fuente
Gracias, no sabía que podía asignar variables en línea de esa manera. Además, si descarta la drop=Fdeclaración, no funciona para subconjuntos de solo una fila. Nunca trabajé scanantes, y asumí que funcionaría así, mi mal. Cambiándolo a una función con nombre.
JAD
También cambió la salida para devolver los índices de la solución, ahorrando 2 bytes más.
JAD
En general, no necesita usar funciones con nombre (a menos que estén anidadas). Además, si asigna el contador de filas como un argumento implícito para la función, puede omitir nuevamente los corchetes:function(x,n=nrow(x))for(i in 1:n)for(j in 1:ncol(z<-combn(n,i)))if(all(colSums(x[k<-z[,j],,drop=F])==1))cat(k)
Billywob
Ah cierto, pensé en hacer eso, npero de alguna manera se me olvidó. Gracias de nuevo :)
JAD
0

APL (Dyalog) , 81 bytes

{×≢⍉⍵:⍵∇{~1∊⍵:00s←⍺⍺c/⍺⌿⍨r←~∨/⍺/⍨~c←~,⍺⌿⍨f←<\⍵:⍺∇f<⍵⋄fr\s},⍵/⍨<\n=⌊/n←+⌿⍵⋄∧/⍵}

Pruébalo en línea!

{ función anónima:

: Si…

   Si el argumento

   cuando transpuesto

   tiene un recuento de filas

  × lo cual es positivo

 entonces

  ⍵∇{... luego aplique esta función con el argumento derecho como argumento izquierdo (matriz de restricción), pero solo después de que haya sido modificado por el siguiente operador anónimo (función de orden superior):
   : si ...
    1∊⍵ hay unos en el argumento correcto
    ~ NO
   entonces ...
    0 devuelva cero (es decir, falla) de lo
    contrario:
   : si ...
    <\⍵ el primer verdadero del argumento correcto (literalmente, acumulado menor que; primera fila)
    f← asigne eso a f
    ⍺⌿⍨  use eso para filtrar las filas del argumento izquierdo
    , ravel (flatten)
    ~ negate
    c← asignar eso a c
    ~  negate
    ⍺/⍨ usar eso para filtrar las columnas del argumento izquierdo, ¿
    ∨/ qué filas tienen un verdadero? (O reducción)
    ~ niega que
    ⍺⌿⍨ use eso para filtrar las filas del argumento izquierdo
    c/ use c para filtrar las columnas que
    ⍺⍺ aplican la función externa original (el operando izquierdo; cubiertas de
    s← submatriz ) asigne eso a s
    0≡  ... es idéntico a cero (falla), luego (intente un fila diferente):
    f<⍵ argumento derecho Y NO f
    ⍺∇  recurse en eso (preservando el argumento izquierdo original)
    más:
    r\s use ceros en r para insertar columnas llenas de cero en s
    f∨  return f O eso (éxito; fila f incluida)
  }... ... en

  +⌿⍵ la suma del argumento

  n← asignar eso a n

  ⌊/ el mínimo de eso

  n= Booleano donde n es igual a eso

  <\ el primero de ellos (lit. acumulativo menor que)

  ⍵/⍨ use eso para filtrar las columnas del argumento (da la primera columna con la menor cantidad)

  , desentrañar eso (aplanar)

 más

  ∧/⍵ filas que son todas unas (ninguna, por lo que esto da un cero para cada fila)

} fin de la función anónima

Adán
fuente