Encontre as linhas que fazem cada coluna ter um True (was: Knuth's Algorithm X)

8

Tarefa

Dada uma matriz booleana, encontre um (ou opcionalmente mais) subconjunto (s) de linhas que tenham exatamente um True em cada coluna. Você pode usar qualquer algoritmo , mas deve suportar matrizes muito grandes, como no último exemplo.

Um algoritmo possível ( algoritmo X de Knuth )

Embora não exista nenhum requisito para usar esse algoritmo, pode ser sua melhor opção.

  1. Se a matriz A não tiver colunas, a solução parcial atual é uma solução válida; terminar com sucesso.
  2. Caso contrário, escolha uma coluna c .
  3. Escolha * uma linha r tal que A r , c = 1.
  4. Inclua a linha r na solução parcial.
  5. Para cada coluna j de tal modo que um R , j = 1,
     para cada linha i tal que A i , j = 1,
      fila de exclusão i a partir da matriz Uma .
     de exclusão da coluna j da matriz A .
  6. Repita este algoritmo de forma recursiva na matriz reduzida A .

* A etapa 3 é não determinística e precisa ser retornada no caso de uma falha em encontrar uma linha em uma chamada posterior da etapa 3.

Entrada

Qualquer representação desejada da matriz 2 × 2 mínima A , por exemplo, como uma matriz numérica ou 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

ou como coleção Universe + Set

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]
    }

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

Resultado

Qualquer representação desejada de uma (ou opcionalmente mais / todas) das soluções, por exemplo, como matriz numérica ou booleana das linhas selecionadas

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

ou como lista booleana indicando linhas selecionadas {0, 1, 0, 1, 0, 1}ou como lista numérica (0 ou 1 indexada) de linhas selecionadas {2, 4, 6}ou como lista de nomes de conjuntos ['B', 'D', 'F'].

Mais exemplos

No:

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

Fora: 1 3 ou 4ou 1 0 1 0ou 0 0 0 1ou [[1,3],[4]etc.


No:

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

Fora: 1 1 0 0 etc.


No:

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

Fora: 0 0 0 1 1 etc.


No:

0 1 1
1 1 0

Saída: Nada, erro ou solução defeituosa, ou seja, você não precisa lidar com entradas sem solução.


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

Fora: 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


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

Fora: 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ão
fonte
4
" Somente soluções usando esse algoritmo são elegíveis para ganhar ", mas o que conta exatamente como " esse algoritmo "? Quão literalmente é necessário tomar " excluir linha " e " excluir coluna "? E o algoritmo precisa usar a heurística, que é uma parte essencial da apresentação do algoritmo por Knuth, mas que não é mencionada na sua descrição?
Peter Taylor
6
Talvez seja melhor fazer uma pergunta que apenas solicite cobertura exata do conjunto, mas que tenha alguns casos de teste robustos que não podem ser manipulados por força bruta ingênua, mas que podem ser manipulados pelo algoritmo de Knuth.
Peter Taylor
1
Todos os algoritmos agora são igualmente permitidos.
Adám
1
"deve suportar matrizes muito grandes" é bastante ambíguo, especialmente porque o algoritmo de Knuth não pode lidar com o grande caso de teste sem a heurística de seleção de coluna. Talvez tenha essa pergunta como puro código de golfe e outra como código mais rápido ?
Angs

Respostas:

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 as capas de maneira não determinística, em profundidade primeiro na mônada da lista. Use headpara calcular apenas um, pois Haskell é preguiçoso. 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 obter mais velocidade usando a sugestão de Knuth de selecionar a coluna com menos, use o seguinte: (115 bytes, lista simples para o universo). Encontra a primeira solução para o grande problema de cobertura do pentomino em menos de um minuto quando compilado.

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]]

Obrigado ao @Zgarb por salvar 1 + 3 bytes!

Agradeço a @ChristianSievers por seu sábio conselho e por economizar 5 bytes e mais.

Ungolfed (com 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
fonte
Pode valer a pena adicionar algumas explicações sobre como isso funciona para pessoas não familiarizadas com Haskell. Você está usando a mônada da Lista para lidar com o não-determinismo, eu acho?
Você pode salvar 3 bytes alterando a filterlista de compreensão e definindo uma função auxiliar h!x=h(`elem`(x>>=id)).
Zgarb
1
@ChristianSievers Estou enfrentando a restrição de monomorfismo (!)=elem, daí o a's. E sim, f pode definitivamente ser usado lá. Obrigado! As diferentes combinações de filter … elemimploram para serem unificadas ...
Angs
1
Podemos voltar ao universo plano, usar a versão que geralmente deve ser mais rápida, mas não faz diferença no grande exemplo, e salvar alguns bytes usando w%a=[c:s|(u:_)<-[sortOn length.group.sort$w++concat a],c<-id&u$a,s<-(w\\c)%(not&c$a)]. Observe que agora ué uma lista que pode conter a coluna escolhida repetidamente, mas isso não importa pela correção.
Christian Sievers
1
@ChristianSievers hooray, menos de + 50% de comprimento, de lento a rápido! Houve uma ligeira regressão na velocidade quando ufoi incorporada, uma vez que é calculada uma vez por elemento a, mas estamos buscando a velocidade do golfe, não a velocidade ideal. c\\b==cprovavelmente não é tão ruim, pois pode parar preguiçosamente. Não incluir ue usar Data.Map.Strictpara encontrar o elemento mais raro estaria em um nível 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 é a função a ser chamada com a coleção Universe + Set.

Jogou um pouco desta 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
fonte
Você deve ser capaz de remover o elenco para listno primeiro loop for e yield, e mudar reversed(...)para...[::-1]
Blue
Toda vez que você usa, S.append(x)você pode fazer S+=x,(com a vírgula à direita): por exemplo C+=X.pop(j),.
FlipTack
1

R, 124 117 115 113 bytes

Muito ineficiente, mas não muito longo no código. Tenta todos os subconjuntos possíveis de linhas e verifica se todas as linhas somam 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 uma matriz como entrada. Retorna os números de rown da primeira solução encontrada. Não retorna nada se não houver soluções, mas pode demorar muito para terminar se a entrada for grande.

Ungolfed:

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 salvos graças a Billywob

Outros 2 bytes salvos graças a Billywob

JAD
fonte
Obrigado, eu não sabia que você poderia atribuir variáveis ​​em linha assim. Além disso, se você soltar a drop=Finstrução, ela não funcionará para subconjuntos de apenas uma linha. Eu nunca trabalhei com isso scanantes, e apenas assumi que funcionaria assim, meu mal. Alterando para uma função nomeada.
JAD
Também alterou a saída para retornar os índices da solução, economizando mais 2 bytes.
JAD
Em geral, você não precisa usar funções nomeadas (a menos que estejam aninhadas). Além disso, se você atribuir o contador de linhas como um argumento implícito à função, poderá pular novamente os colchetes: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 25/11/16
Ah, certo, pensei em fazer isso com, nmas de alguma forma isso me passou pela cabeça. Obrigado novamente :)
JAD
0

APL (Dyalog) , 81 bytes

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

Experimente online!

{ função anônima:

: E se…

   Se o argumento

   quando transposto

   tem uma contagem de linhas

  × o que é positivo

 então

  ⍵∇{… Aplique esta função com o argumento da direita como argumento da esquerda (matriz de restrição), mas somente depois de ter sido modificada pelo seguinte operador anônimo (função de ordem superior):
   : se…
    1∊⍵ houver alguma no argumento da direita
    ~ NOT,
   então…
    0 retorne zero (isto é, falha)
    else:
   : se ...
    <\⍵ a primeira verdade do argumento certo (lit. acumulativo menor que; primeira linha)
    f← atribui isso para f
    ⍺⌿⍨  usar isso para filtrar as linhas do argumento esquerdo
    , ravel (achatar)
    ~ negar
    c← atribuir isso para c
    ~  negar
    ⍺/⍨ use isso para filtrar as colunas do argumento esquerdo
    ∨/ que linhas têm um valor verdadeiro? (Redução OR)
    ~ negam que
    ⍺⌿⍨ use isso para filtrar as linhas do argumento esquerdo
    c/ use c para filtrar as colunas que
    ⍺⍺ aplicam a função externa original (o operando esquerdo; capas de sub-matriz)
    s← atribuam que s
    0≡  … é idêntico a zero (falha) e, em seguida (tente uma linha diferente):
    f<⍵ direito do argumento E NÃO f
    ⍺∇  recurse em que (preservando o argumento original esquerda)
    else:
    r\s zeros uso em r inserir preenchidas com zero colunas s
    f∨  retorno f OR que (o sucesso; fileira f incluído)
  }... ... na

  +⌿⍵ a soma do argumento

  n← atribua isso a n

  ⌊/ o mínimo disso

  n= Booleano onde n é igual a

  <\ o primeiro deles (lit. acumulado menor que)

  ⍵/⍨ use isso para filtrar as colunas do argumento (fornece a primeira coluna com o menor número)

  , emaranhar que (achatar)

 outro

  ∧/⍵ linhas que são todas iguais (nenhuma, portanto, isso dá um zero para cada linha)

} fim da função anônima

Adão
fonte