Aufgabe

Suchen Sie bei einer gegebenen Booleschen Matrix eine (oder optional mehrere) Teilmenge (n) von Zeilen, die in jeder Spalte genau ein True enthalten. Sie können einen beliebigen Algorithmus verwenden , müssen jedoch sehr große Matrizen unterstützen, wie im letzten Beispiel.

Ein möglicher Algorithmus ( Knuths Algorithmus X )

Dieser Algorithmus muss zwar nicht verwendet werden, ist jedoch möglicherweise die beste Option.

1. Wenn die Matrix A keine Spalten enthält, ist die aktuelle Teillösung eine gültige Lösung. erfolgreich beenden.
2. Andernfalls wählen Sie eine Spalte c .
3. Wählen Sie * eine Zeile r so, dass A _{r , c} = 1 ist.
4. Fügen Sie die Zeile r in die Teillösung ein.
5. Für jede Spalte j , so daß A _{r , j} = 1,
    für jede Zeile i , so dass A _{i , j} = 1,
     Zeile löschen i von Matrix A .
    Spalte j aus Matrix A löschen .
6. Wiederholen Sie diesen Algorithmus rekursiv auf der reduzierten Matrix A .

* Schritt 3 ist nicht deterministisch und muss zurückverfolgt werden, wenn bei einem späteren Aufruf von Schritt 3 keine Zeile gefunden wird.

Eingang

Beliebige gewünschte Darstellung der minimalen 2 × 2-Matrix A , z. B. als numerisches oder boolesches Array

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

oder als Universe + Set Sammlung

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

oder als 0 oder 1 indizierte Mengen; {{1, 4, 7}, {1, 4}, {4, 5, 7}, {3, 5, 6}, {2, 3, 6, 7}, {2, 7}}.

Ausgabe

Beliebige gewünschte Darstellung einer (oder optional mehrerer / aller) der Lösungen, z. B. als numerisches oder boolesches Array der ausgewählten Zeilen

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

oder als Boolesche Liste, die ausgewählte Zeilen angibt, {0, 1, 0, 1, 0, 1}oder als numerische (0 oder 1 indizierte) Liste ausgewählter Zeilen {2, 4, 6}oder als Liste von Satznamen ['B', 'D', 'F'].

Mehr Beispiele

Im:

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

Out: 1 3 oder 4oder 1 0 1 0oder 0 0 0 1oder [[1,3],[4]etc.

Im:

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

Out: 1 1 0 0 etc.

Im:

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

Out: 0 0 0 1 1 etc.

Im:

0 1 1
1 1 0

Out: Nichts oder Fehler oder fehlerhafte Lösung, dh Sie müssen keine Eingaben ohne Lösung verarbeiten.

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

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

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

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

Haskell, 100 93 92 87 83 80 Bytes

Knuths Algorithmus:

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]

Berechnet alle Cover nicht deterministisch mit der Tiefe zuerst in der Listenmonade. Verwenden Sie headdiese Option , um nur eine zu berechnen, da Haskell faul ist. Verwendungszweck:

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

Verwenden Sie Folgendes, um mehr Geschwindigkeit zu erzielen, indem Sie Knuths Vorschlag verwenden, die Spalte mit den kleinsten auszuwählen: (115 Byte, flache Liste für das Universum). Findet beim Kompilieren in weniger als einer Minute die erste Lösung für das Problem der großen Pentomino-Abdeckung .

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

Vielen Dank an @Zgarb für das Speichern von 1 + 3 Bytes!

Vielen Dank an @ChristianSievers für seinen weisen Rat und das Einsparen von 5 Bytes und einigen.

Ungolfed (mit flachem Listenuniversum):

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

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 ist die Funktion, die mit der Universe + Set-Sammlung aufgerufen werden soll.

Von dieser Seite ein wenig Golf gespielt

Verwendungszweck:

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

R, 124 117 115 113 Bytes

Sehr ineffizient, aber nicht so lange im Code. Versucht alle möglichen Teilmengen von Zeilen und prüft, ob alle Zeilen 1 ergeben.

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)

Nimmt eine Matrix als Eingabe. Gibt die Rownummern der ersten gefundenen Lösung zurück. Gibt nichts zurück, wenn es keine Lösungen gibt, kann aber lange dauern, bis der Vorgang abgeschlossen ist, wenn die Eingabe groß ist.

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 dank Billywob gespart

Weitere 2 Bytes dank Billywob gespart

APL (Dyalog) , 81 Bytes

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

Probieren Sie es online aus!

{ anonyme Funktion:

 : wenn…

  ⍵ Wenn das Argument

  ⍉ wenn transponiert

  ≢ hat eine Zeilenanzahl

  × das ist positiv

 dann

  ⍵∇{… Wenden Sie diese Funktion dann mit dem rechten Argument als linkes Argument (Einschränkungsmatrix) an, jedoch erst, nachdem sie vom folgenden anonymen Operator (Funktion höherer Ordnung) geändert wurde:
   : Wenn…
    1∊⍵ das rechte Argument
    ~ NICHT vorhanden ist,
   dann…
    0 geben Sie Null zurück (dh fehlgeschlagen)
   ⋄ sonst:
   : wenn…
    <\⍵ das erste wahre des rechten Arguments (wörtlich kumulativ kleiner als; erste Zeile)
    f← das zu f zuweisen, um
    ⍺⌿⍨ die Zeilen des linken Arguments zu filtern
    , ravel (abflachen)
    ~ negieren
    c← , das zu c
    ~  negieren
    ⍺/⍨ Verwenden Sie dies, um die Spalten des linken Arguments zu filtern. Welche
    ∨/ Zeilen haben eine wahre? (ODER Reduktion)
    ~ negieren das
    ⍺⌿⍨ Verwenden Sie das, um die Zeilen des linken Arguments zu filtern.
    c/ Verwenden Sie c , um die Spalten zu filtern,
    ⍺⍺ die die ursprüngliche äußere Funktion anwenden (der linke Operand; Submatrix-Cover).
    s← Weisen Sie zu, dass s
    0≡  … mit Null identisch ist (Fehler). Dann (versuchen Sie a andere Zeile):
    f<⍵ rechts Argument UND NICHT f
    ⍺∇  recurse auf , dass (das ursprüngliche linke Argument Erhaltung)
   ⋄ sonst:
    r\s Verwendung Nullen in r Null gefüllten Spalten einfügen s
    f∨  Rückkehr f OR dass (Erfolg; Zeile f enthalten)
  }... ... auf

  +⌿⍵ die Summe des Arguments

  n← ordne das n zu

  ⌊/ das Minimum davon

  n= Boolescher Wert, wobei n gleich dem ist

  <\ der erste von diesen (wörtlich kumulativ kleiner als)

  ⍵/⍨ Verwenden Sie dies, um die Spalten des Arguments zu filtern (gibt die erste Spalte mit den wenigsten an)

  , ravel das (abflachen)

 ⋄ sonst

  ∧/⍵ Zeilen, die alle Einsen sind (keine, daher ergibt dies für jede Zeile eine Null)

} Ende der anonymen Funktion