Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Repräsentantenliste von Binärmatrizen erzeugen
Autor
Kein bestimmter Bereich Repräsentantenliste von Binärmatrizen erzeugen
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1629
Wohnort: Chile, Ulm
  Themenstart: 2021-07-04

Ich betrachte \(n\!\times\! n\)-Matrizen mit Einträgen in \(\{0,1\}\), wobei zwei dieser Matrizen äquivalent sein sollen, wenn die eine durch Umstellung ihrer Zeilen und Spalten in die andere überführt werden kann. Ich suche einen halbwegs anständigen Algorithmus, der mir eine Repräsentantenliste der entsprechenden Äquivalenzklassen liefert, also eine Liste von Matrizen mit genau einer Matrix von jeder Äquivalenzklasse: jede mögliche Matrix mit \(\{0,1\}\)-Einträgen soll durch Umstellungen in genau eine Matrix der Liste überführbar sein. Ist so ein Algorithmus bekannt? Auf den ersten Blick (und auch auf meinen zweiten) fallen mir nur triviale Vorgehensweisen ein, die ätzend langsam wären, wie zB alle möglichen Matrizen erzeugen, für jede Matrix alle Umstellungen ausprobieren und sie mit allen anderen Matrizen vergleichen. Fällt jemandem von euch besseres ein? (Der Algorithmus muss in Python3 umsetzbar sein, also helfen mir keine Softwareangebote oder ähnliches, was nicht quelloffen ist)


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3009
  Beitrag No.1, eingetragen 2021-07-04

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Hallo, wenn ich das Problem richtig verstehe, dann sollen zwei $n\times n$-Matrizen $A,B$ äquivalent sein, genau dann, wenn es $n\times n$-Permutationsmatrizen $P,Q$ gibt mit $A=PBQ$. Seien $M,N$ zwei disjunkte Mengen mit jeweils $n$ Elementen, wobei wir uns die Elemente von $M$ als Spalten- und die von $N$ als Zeilenindizes zwischen $1$ und $n$ vorstellen. Wir können jede Matrix $A$ auffassen als einen bipartiten Graphen mit Knotenmenge $M\cup N$, wobei zwischen $m\in M$ und $n\in N$ genau dann eine Kante verlaufen soll, wenn $A_{m,n}=1$. Dann sind zwei Matrizen $A,B$ genau dann äquivalent, wenn es zwischen ihren Graphen einen Isomorphismus $f$ gibt mit $f(M)=M$ und $f(N)=N$. Eine Repräsentantenliste für die Graphen sollte man mit folgendem Ansatz bestimmen können, wobei ich mir aber noch nicht alle Details überlegt habe: Wenn wir auf $M$ und $N$ jeweils eine totale Ordnung wählen, dann ist jeder bipartite Graph auf $M\cup N$ äquivalent zu einem Graphen $G$ auf $M\cup N$, bei dem sowohl in $M$ als auch in $N$ die Gradzahlen mit der gewählten Ordnung verträglich sind, d.h. für $m_1,m_2\in M$ und $n_1,n_2\in N$ gilt $m_1\leq m_2 \implies\deg(m_1) \leq \deg(m_2)$ und $n_1 \leq n_2 \implies \deg(n_1)\leq\deg(n_2)$. Es genügt also alle Graphen mit dieser Eigenschaft aufzulisten und aus dieser Liste dann gegebenenfalls noch äquivalente Graphen zu filtern (wobei letzteres vermutlich der schwierige Teil ist). \(\endgroup\)


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3891
Wohnort: Raun
  Beitrag No.2, eingetragen 2021-07-04

Das wäre die Folge https://oeis.org/A002724. Vielleicht sind dort in den Links Hinweise enthalten, wie man eine Liste von Repräsentanten erhält. Viele Grüße, Stefan


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1629
Wohnort: Chile, Ulm
  Beitrag No.3, vom Themenstarter, eingetragen 2021-07-05

\quoteon(2021-07-04 14:10 - StefanVogel in Beitrag No. 2) Das wäre die Folge https://oeis.org/A002724. Vielleicht sind dort in den Links Hinweise enthalten, wie man eine Liste von Repräsentanten erhält. \quoteoff Vielen Dank, das beantwortet meine Frage (Korrektur: leider doch nicht). Ich beobachte freilich, dass die Aufgabe schwerer als geahnt ist und einige Leute es vorziehen, fertige Repräsentantenlisten aus irgendeiner Datenbank abzulesen. Das genügt mir, ich könnte sowieso nur bei Matrizen mit \(n\le6\) etwas Nützliches anfangen. \quoteon(2021-07-04 09:59 - Nuramon in Beitrag No. 1) Wenn wir auf $M$ und $N$ jeweils eine totale Ordnung wählen, dann ist jeder bipartite Graph auf $M\cup N$ äquivalent zu einem Graphen $G$ auf $M\cup N$, bei dem sowohl in $M$ als auch in $N$ die Gradzahlen mit der gewählten Ordnung verträglich sind, d.h. für $m_1,m_2\in M$ und $n_1,n_2\in N$ gilt $m_1\leq m_2 \implies\deg(m_1) \leq \deg(m_2)$ und $n_1 \leq n_2 \implies \deg(n_1)\leq\deg(n_2)$. Es genügt also alle Graphen mit dieser Eigenschaft aufzulisten und aus dieser Liste dann gegebenenfalls noch äquivalente Graphen zu filtern (wobei letzteres vermutlich der schwierige Teil ist). \quoteoff Wir können das Problem auch (ein wenig) vereinfachen, indem wir nur Matrizen mit konstanter Anzahl von 1 suchen. Aber wie du bereits sagst, das Herausfiltern ist die wahre Arbeit, die sich anscheinend nicht immer lohnt (ich möchte ja nur sicherstellen, dass ich keine relevante Matrix vergesse).


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1629
Wohnort: Chile, Ulm
  Beitrag No.4, vom Themenstarter, eingetragen 2021-08-15

\quoteon(2021-07-05 17:53 - Goswin in Beitrag No. 3) \quoteon(2021-07-04 14:10 - StefanVogel in Beitrag No. 2) Das wäre die Folge https://oeis.org/A002724. Vielleicht sind dort in den Links Hinweise enthalten, wie man eine Liste von Repräsentanten erhält. \quoteoff Vielen Dank, das beantwortet meine Frage (leider doch nicht). Ich beobachte freilich, dass die Aufgabe schwerer als geahnt ist und einige Leute es vorziehen, fertige Repräsentantenlisten aus irgendeiner Datenbank abzulesen. Das genügt mir, ich könnte sowieso nur bei Matrizen mit \(n=5\) etwas Nützliches anfangen. \quoteoff Ich aktualisiere diesen Themenstrang. In den Hinweis von StefanVogel habe ich hineingeschaut, aber dort keine Auflistung von Repräsentanten für die Matrizenklassen gefunden. Wie gesagt interessiere ich mich hauptsächlich für 5x5-Matrizen. Wenn ich aber die \(2^{25}=33'554'432\) möglichen 5x5-Binärmatrizen durchgehen würde und jede derselben auf deren \(5!\cdot5!=14400\) Umstellungen untersuche, dann braucht mein Rechner dafür schätzungsweise ein Jahr (immerhin weniger als das Alter des Universums 😁). Für 4x4-Matrizen schafft er das in ungefähr 6_Minuten. Ich kann im Handumdrehen sämtliche infrage kommenden "Signaturen" von solchen Matrizen erstellen (kein Standardausdruck: mit "Signatur" meine ich die geordnete Anzahl der 1-Einträge pro Zeile und Spalte). Aber ich habe keinen annehmbaren Algorithmus gefunden, um Vertreter der Äquivalenzklassen mit vorgegebener Signatur zu erzeugen. Vertreter von Äquivalenzklassen können über eine Totalordnung der Binärmatrizen definiert werden. Von denen gibt es ja viele, aber es wäre gut, wenn so eine Totalordnung (1) leicht zu handhaben und (2) mit einer Totalordnung der Signaturen kompatibel wäre. Ich benutze derzeit nur die triviale Totalordnung (zeilenweise Einträge einer Matrix als Binärzahl interpretieren) aber besondere Vorteile hat die keine. Natürlich ist derzeit kein polynomialbeschränkter Algorithmus für diese Aufgabe bekannt. Aber ich brauche ja keinen solchen, und für 5x5-Matrizen sollte es doch schneller als in einem Jahr gehen, oder?


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3009
  Beitrag No.5, eingetragen 2021-08-16

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Mit folgendem Code (der sich bestimmt noch optimieren lässt) kann ich für $n\leq 4$ in wenigen Sekunden Repräsentantenlisten bestimmen. Für $n=5$ dauert es ca. 20 Minuten. Der Algorithmus berechnet iterativ aus einer Repräsentantenliste der $n\times n$-Matrizen mit $k$ Eins-Einträgen eine Repräsentantenliste der $n\times n$-Matrizen mit $k+1$ Eins-Einträgen. Außerdem wird benutzt, dass man durch Vertauschen von Nullen und Einsen annehmen kann, dass höchstens die Hälfte aller Einträge jeder Matrix den Wert $1$ haben. \sourceon Python \numberson import numpy as np from itertools import permutations import functools # falls Matrix x keinen Repräsentanten in repset hat, # dann füge x zu repset hinzu def add_new_rep(repset,x): n = x.shape[0] perms = [list(p) for p in permutations(range(n))] for p1 in perms: for p2 in perms: y = x[p1][:,p2] z = tuple(y.reshape(-1)) if z in repset: return repset.add(tuple(x.reshape(-1))) # berechne eine Repräsentantenliste # für alle n*n-Matrizen mit genau k Einsen @functools.lru_cache def reps(n,k): if k==0: return [np.zeros((n,n),dtype=int)] if k > n**2/2: return [1-rep for rep in reps(n, n**2-k)] repset = set() for rep in reps(n,k-1): it = np.nditer(rep, flags=['multi_index']) for i in it: if i == 0: y = np.copy(rep) y[it.multi_index]+=1 add_new_rep(repset, y) return [np.array(r).reshape(n,n) for r in repset] # Anzahl der Äquivalenzklassen def count(n): return sum(len(reps(n,k)) for k in range(n*n+1)) for n in range(6): print(n,count(n)) # Ausgabe: # 0 1 # 1 2 # 2 7 # 3 36 # 4 317 # 5 5624 \sourceoff\(\endgroup\)


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3891
Wohnort: Raun
  Beitrag No.6, eingetragen 2021-08-16

Versuche auch mal, ob du folgendes GAP-Programm (https://www.gap-system.org) irgendwo zum Laufen bekommst. Auf meinem Raspberry Pi 4 (sudo apt install gap) schaffe ich die n=4 in 8 Sekunden, doch n=5 bleibt vermutlich wegen Speichermangel stecken: \sourceon GAP P:=[]; P[1]:=Group([()]); P[2]:=Group([(1,3)(2,4),(1,2)(3,4)]); P[3]:=Group([(1,4)(2,5)(3,6),(1,4,7)(2,5,8)(3,6,9),(1,2)(4,5)(7,8),(1,2,3)(4,5,6)(7,8,9)]); P[4]:=Group([(1,5)(2,6)(3,7)(4,8),(1,5,9,13)(2,6,10,14)(3,7,11,15)(4,8,12,16),(1,2)(5,6)(9,10)(13,14),(1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15,16)]); P[5]:=Group([(1,6)(2,7)(3,8)(4,9)(5,10), (1,6,11,16,21)(2,7,12,17,22)(3,8,13,18,23)(4,9,14,19,24)(5,10,15,20,25), (1,2)(6,7)(11,12)(16,17)(21,22), (1,2,3,4,5)(6,7,8,9,10)(11,12,13,14,15)(16,17,18,19,20)(21,22,23,24,25)]); ORBITS:=[]; for n in [1..5] do T:=EnumeratorOfTuples([0,1],n^2); Print("n=",n," Size(ORBITS[n])=\c"); ORBITS[n]:=OrbitsDomain(P[n],T,Permuted); Print(Size(ORBITS[n]),"\n"); od; \sourceoff n läuft von 1 bis n. T bezeichnet die Menge aller nxn-Matrizen mit Einträgen aus {0,1}, worin alle Zeilen einer Matrix hintereinander weg in einer einzigen Zeile zusammengefasst sind. P[n] ist die Permutationsmatrix zur nxn-Matrix, ausgerichtet auf das Speicherformat in T. Schließlich wird in ORBITS[n] die Liste der Äquivalenzklassen bezüglich der Permutation P[n] gespeichert. Davon kann man dann einen Repräsentant jeder Klasse auswählen. Zum Beispiel für n=2 die 7 Repräsentanten \sourceon gap> List(ORBITS[2],i->i[1]); [ [ 0, 0, 0, 0 ], [ 0, 0, 0, 1 ], [ 0, 0, 1, 1 ], [ 0, 1, 0, 1 ], [ 0, 1, 1, 0 ], [ 0, 1, 1, 1 ], [ 1, 1, 1, 1 ] ] \sourceoff und daraus dann wieder quadratische Matrizen zusammensetzen: alles Null, rechts unten 1, untere Zeile 1, rechte Spalte 1, links unten und rechts oben 1, drei Einsen, vier Einsen. P[n] ist eine Gruppe, die ich jeweils aus vier Permutationen erzeuge: 1. Permutation: erste und zweite Zeile tauschen. 2. Permutation ab n=3: alle Zeilen einmal zyklisch vertauschen. 3. Permutation: erste und zweite Spalte tauschen. 4. Permutation ab n=3: alle Spalten einmal zyklisch vertauschen. [Die Antwort wurde nach Beitrag No.4 begonnen.]


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2964
  Beitrag No.7, eingetragen 2021-08-16

Etwa 10.5 Minuten auf meinem Laptop. \sourceon Python \numberson from itertools import permutations from typing import List, Set # Helper function to print a matrix representation of the binary matrix def intToBinaryMatrix(representant: int) -> List[int]: global N matrix = [[0 for r in range(N)] for c in range(N)] for k in range(N*N): r,c = k//N, k%N matrix[r][c] = 1 if (representant & 1 << k) else 0 return matrix # Create the whole set of equivalent matrices, given a binary matrix "representant" def equivalenceClass(representant: int) -> Set[int]: global N, perm ec = set() for rowPerm in perm: for colPerm in perm: permuted = 0 for r in range(N): for c in range(N): if representant & 1<<(N*rowPerm[r]+colPerm[c]): permuted += 1<<(N*r+c) ec.add(permuted) return ec # Create the list of one representant of each equivalence class def buildEquivalenceClasses() -> List[int]: global N total = 1<<(N*N) classRepresentants = [] allRepresentants = [False for k in range(total)] print(f"Processing {total=} matrices.") progress = 0 TH = 1e9 T0 = time_ns() for k in range(total): T = time_ns() if T - T0 > TH: print(f"Progress: {(100*progress)/total:.2f}%; Used {(T-T0)//1e9}s") TH += 1e9 # Check if matrix k is already marked if allRepresentants[k]: continue # If not marked, it is a new representant classRepresentants.append(k) # Build equivalence class of k ec = equivalenceClass(k) # Mark all equivalent matrices for repr in ec: allRepresentants[repr] = True progress += len(ec) return classRepresentants from time import time_ns if __name__ == "__main__": for N in range(1,6): perm = list(permutations(range(N))) EC = buildEquivalenceClasses() print(f"{N=} -> {len(EC)=}") with open(f"binary_class_{N}x{N}.txt","w") as f: for repr in EC: f.write(f"{intToBinaryMatrix(repr)}\n") """ Processing total=2 matrices. N=1 -> len(EC)=2 Processing total=16 matrices. N=2 -> len(EC)=7 Processing total=512 matrices. N=3 -> len(EC)=36 Processing total=65536 matrices. Progress: 88.26%; Used 1.0s N=4 -> len(EC)=317 Processing total=33554432 matrices. Progress: 0.00%; Used 1.0s Progress: 0.01%; Used 2.0s ... Progress: 100.00%; Used 629.0s N=5 -> len(EC)=5624 """ \sourceoff


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1629
Wohnort: Chile, Ulm
  Beitrag No.8, vom Themenstarter, eingetragen 2021-08-16

@Nuramon, StefanVogel, DerEinfaeltige: Vielen Dank; ich bin schwer beeindruckt über wie schnell das beantwortet wurde! Natürlich werde ich jetzt erst einmal etwas Zeit brauchen, um eure Algorithmen zu verstehen und anzuwenden; ich melde mich dann noch einmal.


   Profil
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Goswin hatte hier bereits selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]