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.
- Si la matriz A no tiene columnas, la solución parcial actual es una solución válida; terminar con éxito
- De lo contrario, elija una columna c .
- Elija * una fila r tal que A r , c = 1.
- Incluya la fila r en la solución parcial.
- 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 . - 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 4
o 1 0 1 0
o 0 0 0 1
o [[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
Respuestas:
Haskell,
1009392878380 bytesAlgoritmo de Knuth:
Calcula todas las cubiertas de manera no determinante en profundidad en la mónada de la lista. Use
head
para calcular solo uno ya que Haskell es vago. Uso: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.
¡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):
fuente
filter
comprensión de una lista y definiendo una función auxiliarh!x=h(`elem`(x>>=id))
.(!)=elem
, por lo tanto, ela
's. Y sí, definitivamente se puede usar f allí. ¡Gracias! Las diferentes combinaciones defilter … elem
rogar se unifiquen ...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 ahorau
es una lista que puede contener la columna elegida repetidamente, pero eso no importa para la corrección.u
estaba en línea, ya que se calcula una vez por elementoa
, pero apuntamos a la velocidad de golf, no a la velocidad óptima.c\\b==c
probablemente no sea tan malo ya que puede detenerse perezosamente. No alinearu
y usarData.Map.Strict
para encontrar el elemento más raro estaría en un nivel totalmente diferente.Python, 482 bytes
r
es la función para llamar con la colección Universe + Set.Golfé un poco desde esta página
Uso:
fuente
list
en el primer bucle for y el rendimiento, y cambiarreversed(...)
a...[::-1]
S.append(x)
puede hacerS+=x,
(con la coma final): por ejemploC+=X.pop(j),
.R,
124117115113 bytesMuy ineficiente, pero no tanto en código. Intenta todos los subconjuntos posibles de filas y comprueba si todas las filas suman 1.
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:
7 bytes guardados gracias a Billywob
Otros 2 bytes guardados gracias a Billywob
fuente
drop=F
declaración, no funciona para subconjuntos de solo una fila. Nunca trabajéscan
antes, y asumí que funcionaría así, mi mal. Cambiándolo a una función con nombre.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)
n
pero de alguna manera se me olvidó. Gracias de nuevo :)APL (Dyalog) , 81 bytes
Pruébalo en línea!
{
función anónima::
Si…⍵
Si el argumento⍉
cuando transpuesto≢
tiene un recuento de filas×
lo cual es positivoentonces
⍵∇{
... 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~
NOentonces ...
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)~
negatec←
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 izquierdoc/
use c para filtrar las columnas que⍺⍺
aplican la función externa original (el operando izquierdo; cubiertas des←
submatriz ) asigne eso a s0≡
... 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 sf∨
return f O eso (éxito; fila f incluida)}
... ... en+⌿⍵
la suma del argumenton←
asignar eso a n⌊/
el mínimo de eson=
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ónimafuente