Symmetrische 0-1-Matrizen erstellen

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Etti

Forum-Newbie


	Beiträge: 4

	Anmeldedatum: 27.12.16

	Wohnort: ---

	Version: GNU Octave, version 3.8.0

Verfasst am: 27.12.2016, 19:02 Titel: Symmetrische 0-1-Matrizen erstellen

Hallo zusammen,

ich bin neu hier und nutze seit wenigen Wochen octave auf meinem Mac.
Ich kenne mich da noch nicht so gut aus und habe dementsprechend ein Problem.
Und zwar folgendes:

Ich möchte gern symmetrische Matrizen erstellen, die nur 0 und/oder 1 enthalten. Alle möglichen Kombinationen. Angefangen von 2x2-Matrix bis hin zur 8x8-Matrix.

D.h. ich erwarte, dass mir bei der Größe 2x2 am Ende 8 symmetrische Matrizen angezeigt werden (1 Matrix mit nur 0en, 2 Matrizen mit einer 1, 2 M. mit zwei 1en, 2 M. mit drei 1en und 1 Matrix mit nur 1en). Das Ergebnis kenne ich, weil ich die mir aufgemalt habe. Für 3x3-Matrizen wird es ja schon schwieriger, weil es viel viel mehr Möglichkeiten gibt. Ganz zu schweigen von den Möglichkeiten bei 8x8-Matrizen :O

Außerdem möchte ich gerne zu jeder einzelnen Matrix den Rang haben. Muss man das vorher prüfen? Kann man das im Befehl einbauen?

Gibt es einen oder mehrere octave-Befehle dazu?
Funktioniert das anhand einer Schleife?

Der Vollständigkeit halber:
Wie man prüft, ob eine Matrix überhaupt symmetrisch ist, weiß ich, z.B.:

Code:

A=[1,0;0,0]

B=A'*A

if all (A'==A)
'wahr'
else
'falsch'
end

Funktion ohne Link?

Ich wäre für weitere Tipps und Hinweise sehr dankbar Smile

Schönen Gruß
Etti

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 28.12.2016, 13:31 Titel: Re: Symmetrische 0-1-Matrizen erstellen

Hallo Etti,

Bei allen Permutations-Problemen muss man zunächst nachdenken.
[Denkpause] :-)
Eine 8x8-Matrix hat 64 Elemente. Wenn sie 0 und 1 sein können, gibt es 2^64 Möglichkeiten. Das sind 18'446'744'073'709'551'616, also etwa 18 Trilliarden. Wenn Du einen schnellen Rechner hast und die Lösung effizient geschrieben hast, schaffst Du vielleicht eine Milliarden Tests pro Sekunde. Dann läuft das Programm etwa 18'446'744'073 Sekunden, also 584 Jahre.
Du kannst einen Rechen-Cluster mieten mit 1000 Knoten. Dann wärst Du in einem halben Jahr fertig. Das kostet aber eine Menge Geld.
Über wieviel Zeit und Geld verfügst Du?

Nun suchst Du ja nach symmetrischen Matrizen. Anstatt alle Matritzen zu erstellen und die gigantische Anzahl unsymmetrischer zu verwerfen, wäre es doch viel praktischer, gleich nur symmetrische zu erstellen. Das sind schon viel weniger, nämlich 2^36. Die 36 ist dabei die 8.te "Dreieckszahl" (siehe WikiPedia), n*(n+1)/2. Symmetrische Matrizen haben den Vorteil symmetrisch zu sein. Klingt trivial. Ist es auch :-)
Es reicht also sich z.B. die rechte obere Dreiecks-Matrix zu merken und die linke untere durch Spiegeln zu erzeugen. Bei eine 8x8-Matrix hat die rechte obere (mit der Diagonalen) 36 Elemente. Wenn Du hier also jeweils 1 und 0 einfüllst, gibt es 2^36 Möglichkeiten und damit genauso viele symmetrische Matrizen.

Nun gibt es dafür 68'719'476'736, also ~68 Milliarden, Möglichkeiten und das ist dann keine Sache mehr von Jahren. Aber so viele Matrizen zu speichern ist nicht einfach, immerhin brauchst Du 64*8+100 Byte pro Matrix (die 100 Byte sind ungefähr der Overhead, den Matlab pro Variable zur Verwaltung anlegt) und eine Zahl benötigt 8 Byte, wenn sie als DOUBLE gespeichert wird. Das sind etwa 42 TerraByte. Da brauchst Du also schon einen Satz moderner 10TB Festplatten.
Hm. Und die willst Du dann mit symmetrischen Matrizen voll schreiben?!
Du könntest uint8 verwenden statt double und benötigst dann nur noch ein Achtel des Speichers. Noch einfacher wäre es allerdings, Du speicherst gleicht nur die Bitfolge der oberen Dreiecks-Matrix. bei 36 Bit benötigst Du einen uint64 oder einen double pro Matrix. Und das Programm dazu wird sehr überschaubar:

Code:

Result = 1:2^36;

Funktion ohne Link?

Das braucht 549 GigaByte im RAM. Dazu braucht man sinnvollerweise etwa 1TB freies RAM, damit man mit den Zahlen auch noch arbeiten kann. Immer noch keine alltägliche Maschine, aber machbar.

Das Ergebnis ist aber so trivial, dass ich mich frage, wozu Du das überhaupt speichern willst.
Erkläre das mal. Vermutlich lässt sich Dein Problem effizienter lösen.

Gruß, Jan

PS. Ist klar geworden, warum jede Permutations- bzw. Kombinations-Aufgabe zunächst ein Problem für eine Tasse Kaffee, ein kleines Blatt Papier und einen Bleistift ist? Man kann so vermeiden, mal eben den Rechner für 500 Jahre lahmzulegen. Exponentielles Wachstum von Problemen ist etwas, dem man nur mit Nachdenken beikommen kann.

Etti

Themenstarter

Forum-Newbie


	Beiträge: 4

	Anmeldedatum: 27.12.16

	Wohnort: ---

	Version: GNU Octave, version 3.8.0

Verfasst am: 28.12.2016, 14:06 Titel:

Auweia, wenn ich mir die Dimensionen so anschaue, in denen ich mich bewegen würde - nein, ich verfüge weder über die Zeit noch das Geld noch die technische Ausstattung... Wink

Es geht also insgesamt darum, dass ich in eine größere Aufgabe zu lösen habe. Es geht um die Betrachtung von Matrizen in verschiedenster Weise.
Zu Beginn muss ich aber alle 0-1-Kombimöglichkeiten von symmetrischen Matrizen (deren Rang gleich ihrer Anzahl von Nichtnullzeilen ist) bis max. 8x8 aufsteigend enumerieren - mittels mehrerer Schleifen.
Es ist schon ganz richtig, dass mir die Matrizen angezeigt und der Datensatz gespeichert werden soll.
Gestern habe ich folgendes Programm für 3x3-Matrizen zum Laufen gebracht, ich erhalte das gewünschte Ergebnis: 64 symmetrische 3x3-Matrizen mit jeder möglichen 0-1-Kombination.
Nun, für 8x8-Matrizen brauch ich dann gleich 36 Vorschleifen, richtig? Smile

Und dazu kommen noch die Funktionen, dass der Rang geprüft und die Anzahl der Nichtnullzeilen gezählt werden müssten.
Allerdings würde ich jetzt sagen (ohne zu wissen, wie das geht), dass diese Funktionen nichts weiter als ausgelagert werden sollten. Vielleicht auch die Schleifen? Also so wie Klassen bei Java? Sorry, ich habe nur wenig Ahnung von der Materie...

Hier mal mein Code:

Code:

for i=0:1:1
for j=0:1:1
for k=0:1:1
for l=0:1:1
for m=0:1:1
for n=0:1:1
A = [i,j,k;j,l,m;k,m,n]
end
end
end
end
end
end

Funktion ohne Link?

Ich verstehe ehrlich gesagt nicht so genau, wie ich da jetzt uint8 statt double einbaue... ?

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 28.12.2016, 15:17 Titel:

Hallo Etti,

Zitat:

Es geht also insgesamt darum, dass ich in eine größere Aufgabe zu lösen habe.

Und was ist diese Aufgabe genau?
Was bringt es Dir 68 Milliarden Matrizen mitsamt ihren Eigenschaften im Commandwindow anzeigen zu lassen, wenn nie ein Mensch es schaffen wird, das zu lesen? So einen Trumm auf riesige Festplatten zu speichern ist ebenfalls ziemlich redundant, weil man die Eigenschaften so leicht on-the-fly berechnen kann. Wozu dient also diese gigantische Tabelle an Daten?

Zitat:

Zu Beginn muss ich aber alle 0-1-Kombimöglichkeiten von symmetrischen Matrizen (deren Rang gleich ihrer Anzahl von Nichtnullzeilen ist) bis max. 8x8 aufsteigend enumerieren - mittels mehrerer Schleifen.

Wieso möchtest Du das mit mehreren Schleifen machten? Das ist mit einer Schleife viel einfacher.

Code:

n = 4; % Number of rows and columns
m = n * (n + 1) / 2;
mask = tril(true(5), 0);

for k = 1:2^m
v = dec2bin(k, m) - '0'; % Can be simplified for speed
M(mask) = v;
...
end

Funktion ohne Link?

So bekommst Du schon mal die rechte obere Dreieckmatrix. Die linke untere lässt sich ähnlich befüllen. Das geht auch noch deutlich effizienter. Aber bevor man sich die Mühe macht, das zu programmieren, sollte wirklich klar sein, wozu das gut ist. Immer die gesamte Matrix neu zu erzeugen und den Rang zu bestimmen, ist ja größtenteils überflüssig, weil man von Iteration zu Iteration ja nur ein Bit ändert. Da es für den Rang nicht auf die Reihenfolge der Zeilen ankommt, werden auch so noch viel zu viele Matrizen erstellt.

Wenn Du das Problem schon für eine NxN-Matrix gelöst hast, kann die Lösung für eine (N+1)x(N+1) Matrix darauf aufbauen, weil ja nur eine neue Spalte und Zeile dazu kommt. Das sollte die Komplexität der Lösung drastisch reduzieren.

Gruß, Jan

Etti

Themenstarter

Forum-Newbie


	Beiträge: 4

	Anmeldedatum: 27.12.16

	Wohnort: ---

	Version: GNU Octave, version 3.8.0

Verfasst am: 28.12.2016, 15:35 Titel:

Zitat:

Und was ist diese Aufgabe genau?

Sinn und Zweck ist mir auch nicht ganz klar. Ich weiß, das klingt total bescheuert! Es ist aber so. Bzgl. konkreter Aufgabeninhalte, PN. Ok?

Zitat:

Wozu dient also diese gigantische Tabelle an Daten?

Im letzten Aufgabenteil geht es um Graphen... Es sollen zu den Beispielmatrizen Graphen gezeichnet werden und diese dann auf Besonderheiten und Struktur untersucht werden.

Die drei Pünktchen ... in deinem Code - inwiefern habe ich da was zu ergänzen?
Der Code direkt im Terminal eingegeben liefert mir:
error: A(I) = X: X must have the same size as I

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 28.12.2016, 17:23 Titel:

Hallo Etti,

Mein Code-Schnipsel war nur zur Anschauung gedacht, wie man das Problem flexibel und effizient mit einer Schleife lösen kann. Es ist immer sinnvoll Code zu schreiben, der nicht von der Größe der Inputs abhängt. Geschachtelte Schleifen fallen damit schon mal aus.

Erinnerst Du Dich an den altenm Gauss, der sich nicht die Mühe machte die Zahlen von 1 bis 100 tatsächlich schriftlich zu addieren? Vielleicht sucht Dein Professor nach findigen Studenten.

Denke mal über die beiden Ideen nach: 1. mit einer FOR-Schleife nur die symmetzrischen Matrizen erzeugen, 2. Ähnlich einer vollständigen Induktion die Fragen für eine NxN-Matrix lösen und dann auf den (N+1)-Fall schließen. Man z.B. kann die Anzahl der symmetrischen Matritzen leicht bestimmen, ohne sie tatsächlich erzeugen zu müssen (siehe oben).
Wenn Du dazu eigene Ideen hast, versuche sie zu implementieren und stelle konkrete Fragen dazu.

Gruß, Jan

Etti

Themenstarter

Forum-Newbie


	Beiträge: 4

	Anmeldedatum: 27.12.16

	Wohnort: ---

	Version: GNU Octave, version 3.8.0

Verfasst am: 28.12.2016, 23:43 Titel:

Hallo Jan,

ich habe nun eine ganz konkrete Frage.
Mit welchem Befehl lasse ich die Anzahl der Nichtnullzeilen einer Matrix addieren und ausgeben?
Es soll jetzt erst einmal egal sein, welche Matrix und wie sie erstellt wurde.

Meine Idee bisher:

Code:

[rowIdcs]=find(A~=0)

Funktion ohne Link?

--> zeigt leider nur die Positionen der Nichtnullelemente

oder

Code:

numberOfNonZeros = nnz(A==1)

Funktion ohne Link?

--> zählt aber leider alle Einsen und nicht zeilenweise...

Edit:

Code:

J=all(A==0, 2);
K=sum(J);
if (B==(H-K))
A
B
I = (H-K)

Funktion ohne Link?

--> ich habs! Aber leider nicht so elegant, wie es hätte sein können. Help!

Gruß
Etti

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 29.12.2016, 13:26 Titel:

Hallo Etti,

Ja, das lässt sich gut beantworten:

Zitat:

Mit welchem Befehl lasse ich die Anzahl der Nichtnullzeilen einer Matrix addieren und ausgeben?

Die Anzahl "addieren"?

Code:

x = randi([0,1], 4, 4) % Testdaten
rowAnyNonZero = any(x, 2); % Zeilen die nicht nur aus 0 bestehen
rowAllNotZero = all(x, 2); % Zeilen, die keine 0 enthalten

Funktion ohne Link?

Und wenn Du dann die Anzahl haben willst, erhältst Du sie mit dem sum Befehl.

Gruß, Jan


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.