Minimale Kostenblockdiagonalisierung

10

Betrachten Sie binäre Blockdiagonalmatrizen , die quadratische Blöcke von 1s auf der Hauptdiagonale haben und überall sonst 0 sind. Nennen wir solche Matrizen "gültige" Matrizen.

Hier sind zum Beispiel einige gültige 4x4-Matrizen:

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

Beachten Sie, dass eine alternative Art der Beschreibung solcher Matrizen darin besteht, dass es eine Kette von quadratischen 1-Blöcken von oben links nach unten rechts gibt, die Ecke zu Ecke berühren und überall sonst 0 ist.

Im Gegensatz dazu sind hier einige ungültige 4x4-Matrizen:

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

Sie werden eine gegeben ndurch nbinäre Matrix als Input - was ist die minimale Anzahl von 0Bits , die Sie einstellen benötigen , 1um eine gültigen Matrix zu bekommen?

Sie können eine Funktion oder ein Programm Mitnahmen in jeder geeigneten Zeichenfolge, Liste oder Matrix - Format schreiben repräsentiert eine ndurchn Matrix von 0 und 1 (solange es nicht vorverarbeitet wird). Zeilen müssen in irgendeiner Weise klar voneinander getrennt sein, sodass Formate wie ein 1D-Array von Bits nicht zulässig sind.

Dies ist Code-Golf , daher ist das Ziel, die Anzahl der Bytes in Ihrem Programm zu minimieren.

Beispiele

Zum Beispiel, wenn die Eingabe ist

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

dann ist die Antwort 5, da Sie fünf 0Bits setzen können, um 1zu erhalten:

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

und dies ist die erforderliche Mindestanzahl. Wenn jedoch die Eingabe war

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

dann ist die Antwort 24, da die einzige gültige 5x5-Matrix, in der oben rechts 1steht, die Matrix aller ist1 s ist.

Testfälle

Tests werden hier als 2D-Array von Ganzzahlen dargestellt.

[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

Anmerkungen

code-golf array-manipulation Sp3000
quelle

Antworten:

3

MATL , 46 43 Bytes

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

Die Eingabe ist ein 2D-Array mit einem Semikolon als Zeilentrennzeichen. Die Eingabe für den letzten Testfall lautet beispielsweise

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Probieren Sie es online aus! Oder überprüfen Sie alle Testfälle (Code leicht geändert, um alle Eingaben zu übernehmen; die Ergebnisse werden nach einigen Sekunden angezeigt).

Erläuterung

Die Eingabe sei eine N × N- Matrix. Der Code berechnet zuerst alle ( N + 1) -Tupel von Blockgrößen, die die entsprechende Matrixgröße erzeugen. Zum Beispiel für N = 4 die Tupel sind 0 0 0 0 4, 0 0 0 1 3..., 4 0 0 0 0. Für jedes Tupel wird die Blockdiagonalmatrix mit diesen Blockgrößen erstellt. Anschließend wird geprüft, ob die Matrix alle 1Einträge in der Eingabe abdeckt , und in diesem Fall die Anzahl der 1Einträge notiert , die in der Eingabe nicht vorhanden waren. Das Endergebnis ist das Minimum aller erhaltenen Zahlen.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each 
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display
Luis Mendo
quelle
3

Python mit Numpy, 102

from numpy import*
lambda M:sum(diff([k for k in range(len(M)+1)if(M|M.T)[:k,k:].any()-1])**2)-M.sum()

Ein effizienter Algorithmus. Findet die "Halspunkte" auf der Diagonale, die Blöcke trennen können. Diese haben alle Nullen oben und rechts sowie unten und links. Die minimalen Blöcke sind die zwischen den Halspunkten.

??000
??000
00???
00???
00???

Die Länge eines Blocks ist die Differenz zwischen aufeinanderfolgenden Halspunkten, also deren Gesamtfläche aus der Summe der Quadrate dieser. Das Subtrahieren der Summe der ursprünglichen Matrix ergibt dann die Anzahl der benötigten Flips von 0 bis 1.

xnor
quelle
2

Pyth, 45 Bytes

[email protected]^+LsYN2d+0._ds.pM./lQss

Schwierige Aufgabe, also ziemlich lang.

Probieren Sie es online aus: Demonstration oder Test Suite

Erläuterung:

s.pM./lQberechnet alle ganzzahligen Partitionen von len(matrix). ms.b^+LsYN2d+0._dwandelt sie in Koordinatenpaare um. Zum Beispiel wird die Partition [1, 2, 2]von in 5konvertiert [[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4].

[email protected]filtert dann nach Partitionen, die die Matrix vollständig überlappen ( .DRlQx1sQberechnet alle Koordinatenpaare der aktiven Zellen in der Matrix).

-hSlM...ss zählt die Zellen jeder verbleibenden Partition, wählt die mit den wenigsten Zellen aus und subtrahiert die bereits aktiven Zellen.

Jakube
quelle
0

Matricks , 180 Bytes (nicht konkurrierend )

Matricks ist ein neuer Esolang, den ich kürzlich erstellt habe, um Matrixprobleme (wie dieses) zu lösen, indem ich nur zwei Datentypen habe: Floats und Matricies. Es ist noch nicht vollständig ausgestattet und es fehlen noch viele Operationen (ich musste einige Funktionen für diese Herausforderung hinzufügen). Wie auch immer, hier ist der Code:

il=1:j3;:bdx;;;s1::L;j1;;
b{q:1;mgr:c;|gc:r;|(r=c)|(gr-1:c;|gr:c+1;)&(rec)|(gr+1:c;|gr:c-1;)&(cer):l:L;};z:(l-1)/2;B1;s1::g1:;-1;ig1:;=0:j2;:j1;;
s1::d{q:1;};;kg1:;-g:;;
kg:;*-1+1;

Erläuterung

Der erste Teil il=1:j3;:...;prüft, ob das Array die Größe 1 hat. Wenn dies der Fall ist, springt es zur letzten Zeile kg:;*-1+1;, was eine einfache 0 <-> 1Funktion ist.

Andernfalls wird mit dem Rest des Codes fortgefahren. bdx;;;Setzt die Zelle 0,0auf die aktuelle Summe und s1::L;j1;erstellt einen Zähler in der Zelle in der Zeile darunter.

Die nächste Zeile ist etwas komplizierter. Es ist eine Schleife, die nmal läuft nund die Größe der Matrix hat. Ich werde den 3. Testfall als Beispiel verwenden. Wenn wir zum ersten Mal in die zweite Zeile kommen, sieht die Matrix folgendermaßen aus:

1 0 1
2 0 0

Zunächst gehen wir auf das Matrixverständnis ein {q:1;m...;}. Dies macht die Diagonale und versucht sein Bestes, um 0 zu bereinigen, die ausgefüllt werden müssen. All dies wird mit einfachen booleschen Operatoren erreicht. Dann stellen wir es der aktuellen Matrix voran und geben Folgendes an:

    V--data we want to keep
1 1 1 0 1 <-|
1 1 2 0 0 <-- old matrix

Dann schneiden wir die alte Matrix mit z:(l-1)/2;und drehen die gesamte Matrix mit nach links B1;. Das gibt uns eine Matrix, die für die nächste Iteration bereit ist und wie folgt aussieht:

1 1 1
2 1 1

Schließlich dekrementieren wir den Zähler, überprüfen ihn und fahren fort ig1:;=0:j2;:j1;;

Sobald die Schleife abgebrochen ist, finden wir die neue Summe und setzen den alten Punkt des Zählers mit s1::d{q:1;};;. Schließlich nehmen wir den Unterschied und kehren zurück kg1:;-g:;;. kSetzt das aktuelle Array auf einen Wert und das Drucken ist implizit.

...

Wie Sie sehen können, ist Matricks ziemlich ausführlich und keine sehr gute Golfsprache . Aber zum Teufel, ich wollte es vorführen.

Blau
quelle