Binäre Orthonormalmatrix

Werbeanzeige

eisenmad

Treue Seele

Beiträge: 84

Wohnort: Heute hier, morgen dort

Beruf: Denker

14.09.2015, 20:37

Binäre Orthonormalmatrix

Hallo

Ich versuche eine Matrix in C++ zu programmieren, mit L Zeilen und N Spalten. Die Koeffizienten sollen nur 0 oder 1 sein und random gewählt werden mit folgender Einschränkung:

Die L Zeilenvektoren sollen alle orthonormal zueinander stehen. Dies ist nur möglich, wenn keine zwei Einser in den Spalten untereinander stehen. Ferner dürfen in keiner Zeile mehr als eine Eins stehen, sonst wäre die Länge nicht mehr Eins.

Zum Beispiel sowas:

0000001
1000000
0000010

Habe bereits viel überlegt aber komme auf keinen grünen Nenner. Wie würde das programmiert werden? Bei einem Beispiel wie hier macht man das natürlich von Hand, aber ich möchte später die Zahl für Zeilen und Spalten ansteigen lassen auf eine Größe die man nicht von Hand machen möchte.

Danke

Zum Seitenanfang

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

14.09.2015, 20:50

Kannst du die Matrix nicht Zeile für Zeile durchlaufen und eine Stelle bestimmen die du zur 1 machen willst und du merkst dir zusätzlich welche Spalten schon 1er enthalten und nimmst diese aus den möglichen Stellen heraus?

„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Zum Seitenanfang

eisenmad

Treue Seele

Beiträge: 84

Wohnort: Heute hier, morgen dort

Beruf: Denker

14.09.2015, 20:56

Hi Schorsch

Habe ich dann die Randomness nicht verloren? Wenn ich das Programm wenns fertig sein wird mehrfach ausführe, dann sollte die Verteilung der 1er anders anders sein (aber trotzdem paarweise zueinander orthonortmale Zeilen).

Zum Seitenanfang

MitgliedXYZ

Alter Hase

Beiträge: 1 369

Wohnort: Bayern

14.09.2015, 21:04

Und wenn du die Stelle, die du zuerst in eine 1 umschreibst zufällig bestimmst?

Zum Seitenanfang

eisenmad

Treue Seele

Beiträge: 84

Wohnort: Heute hier, morgen dort

Beruf: Denker

14.09.2015, 21:18

Daran habe ich auch gedacht, doch ich bekomme das nicht implementiert. Mein C++ ist noch sehr schwach (daran arbeite ich aber)

p.s.

Aber vielleicht könnten wir das zusammen erarbeiten?

Wie man ein 2-dim. Array Zeilen und Spaltenweise durchlaufen lässt weiss ich inzwischen. Nun der Schritt in welchem Random ausgewählt werden könnte welche Stellen 1er werden, wie würde das programmiert werden? Habe leider keinen Ansatz

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »eisenmad« (14.09.2015, 21:35)

Zum Seitenanfang

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

14.09.2015, 22:03

Fang doch erst mal etwas einfacher an und arbeite dich hin. Stell dir vor du hast eine Liste von Musiktiteln und möchtest diese zufällig abspielen. Dabei soll jeder Titel ein mal abgespielt werden bevor sich ein Song wiederholt. Eine Möglichkeit wäre die Liste der Songs zu nehmen und zufällig einen Song daraus zu entfernen und in eine neue Liste zu übertragen. Das machst du so lange bis deine erste Liste leer ist. Die neue Liste enthält nun alle Lieder in zufälliger Reihenfolge.
Das kann man jetzt ein wenig abwandeln. Ich bin mir nicht sicher ob du dich schon mit Listen auskennst. Das ganze funktioniert auch mit einem Array. Und anstatt jetzt mit zwei Arrays zu werkeln kann man das ganze auch mit einem lösen. Als erstes wählst du 1 Element aus dem gesamten Array zufällig aus und tauscht es mit dem Element an der ersten Stelle im Array. Jetzt wählst du als nächstes ein Element zwischen der 2ten und der letzten Stelle aus dem Array aus und tauschst es mit dem Element an der 2ten Stelle. Dann ab der dritten und so weiter bis du das gesamte Array durchlaufen hast. Danach ist das Array gemischt. Als Beispiel:

	Quellcode
1 2 3 4 5	[1, 2, 3, 4, 5] [3, 2, 1, 4, 5] [3, 5, 1, 4, 2] [3, 5, 1, 4, 2] [3, 5, 1, 2, 4]

Stell dir vor in jede Zeile entspricht dem Array nach einem Schritt. Am Anfang hast du die Zahlen von 1 bis 5. Dann wird zufällig ein Element aus dem Array gewählt. In diesem Fall die 3. Diese wird mit dem Element an erster Stelle getauscht. Danach sieht das Array wie in der zweiten Zeile aus. Jetzt nimmst du zufällig ein Element nach dem ersten Element, in diesem Fall die 5 und tauschst sie mit der 2. Dann nimmst du zufällig ein Element nach dem zweiten Element, in diesem Fall die 1. Diese tauschst du mit sich selbst da sie schon an 3ter Stelle steht. Jetzt machst du das ganze noch ein mal für die Elemente nach dem dritten Element wobei die 2 gewählt wurde. Dann bist du beim letzten Element im Array welches du mit sich selbst tauschen würdest weshalb du hier nicht mehr zufällig wählen musst.
Ich hoffe es ist einigermaßen rüber gekommen was ich meine.
Überleg dann danach noch mal wie du an dein Problem herangehen könntest.

„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

14.09.2015, 22:04

Du brauchst nur ein Array mit dem Inhalt [0, 1, 2, ..., N-1]. Dieses Array shuffelst du nun zufällig (siehe hier). Danach wählst du die ersten L Elemente aus. Aus jedem dieser Elemente machst du eine Zeile - der Wert des Elements sagt dir, welche Spalte du auf 1 setzen musst.

David Scherfgens Website | Konzentrationstest Polizei