Reihen einer Matrix (n,m) nach Bedingungen in Gruppen sortieren

09.10.2017, 16:34

vonluetzen

Reihen einer Matrix (n,m) nach Bedingungen in Gruppen sortieren

Meine Frage:
Ich habe eine Matrix (m,n) die nach dem Zufallsprinzip Nullen und Einsen enthält. Die Zeilenanzahl (m) ist ein vielfaches von der Spaltenanzahl (n).
Ich möchte nun die Reihen der Matrix in genau n Untergruppen anordnen, sodass jede der n Untergruppen in einer ihrer Spalten ausschließlich Einsen enthält. Jede Untergruppe sollte demnach eine andere der n Spalten abdecken, also ausschließlich "Einsen" darin stehen haben. Ich möchte auch zweifelsfrei identifizieren wenn eine solche Anordnung unmöglich ist.
Gibt es einen Algorithmus oder eine mathematische Methode mit der ich für beliebig große Matrizen (n,m) und Gruppengrößen (k) solche Lösungen berechnen kann?

Zum Beispiel: Ich habe eine Matrix (9,3):

1 0 0 (Reihe 1)
0 1 1 (Reihe 2)
0 0 1 (Reihe 3)
1 1 0 (Reihe 4)
1 1 1 (Reihe 5)
0 1 0 (Reihe 6)
0 0 1 (Reihe 7)
1 0 1 (Reihe 8)
1 1 0 (Reihe 9)

Eine mögliche Lösung:
Gruppe 1:
1 0 0 (Reihe 1)
1 1 0 (Reihe 4)
1 1 1 (Reihe 5)
Gruppe 2:
0 1 1 (Reihe 2)
0 1 0 (Reihe 6)
1 1 0 (Reihe 9)
Gruppe 3:
0 0 1 (Reihe 3)
0 0 1 (Reihe 7)
1 0 1 (Reihe 8)

Meine Ideen:
1. Identifiziere die Reihen der Matrix die in Spalte n einen Eintrag (1) haben und bilde einen Vektor der den Reihenindex enthält.
2. Selektiere zufällig aus den "Reihen mit Einträgen in Spalte 1" eine Gruppe der Größe k
3. Selektiere aus den "Reihen mit Einträgen in Spalte 2" eine Gruppe k. Keine der selektierten Reihen darf schon in der ersten Gruppe vorgekommen sein
4. Dies muss bis zur letzten Spalte fortgeführt werden.

So weit ist es relativ einfach. Aber was mache ich wenn ich Reihen zwischen Gruppen austauschen muss? Was ist wenn ich keine Gruppe k mehr bilden kann und dafür Reihen aus vorhergegangenen Gruppen austauschen muss?

Ich bin für jeden Denkanstoß dankbar. Vielleicht denke ich zu sehr um die Ecke....

09.10.2017, 17:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von vonluetzen
Ich möchte nun die Reihen der Matrix in genau n Untergruppen anordnen, sodass jede der n Untergruppen in einer ihrer Spalten ausschließlich Einsen enthält.

Eine Frage zu deinem Begriff "Untergruppe": Soll jede dieser Untegruppen gleich viele Zeilen enthalten? Deine Forderung $\begin{align*} n \mid m \end{align*}$ legt diese Vermutung irgendwie nahe.

Zitat:

Original von vonluetzen
Jede Untergruppe sollte demnach eine andere der n Spalten abdecken, also ausschließlich "Einsen" darin stehen haben. Ich möchte auch zweifelsfrei identifizieren wenn eine solche Anordnung unmöglich ist.

Z.B. schon mal dann, wenn es eine Nullzeile gibt. Denn die lässt sich ja offenbar keiner der Gruppen zuordnen.

09.10.2017, 17:17

vonluetzen

Auf diesen Beitrag antworten »

Hallo HAL 9000,

vielen Dank für deine schnelle Antwort. Du hast recht: Aus einer Nullzeile kann ich sofort schließen, dass eine Lösung nicht möglich ist.

Zu deinem ersten Kommentar: Ja jede Untergruppe soll immer gleich viele Zeilen enthalten. So wie im Beispiel, nur mit viel größeren Matrizen....

Viele Grüße,

09.10.2017, 17:26

HAL 9000

Auf diesen Beitrag antworten »

Ok, wenn $\begin{align*} k \end{align*}$ deine einheitliche Gruppengröße ist, dann ist schlicht $\begin{align*} m=n\cdot k \end{align*}$ . Dann mal ein paar Überlegungen von mir:

Sei $\begin{align*} A_j \end{align*}$ die Menge der Nummern derjenigen Zeilen, welche in Spalte $\begin{align*} j \end{align*}$ eine 1 haben.

Für eine Aufteilung wie von dir gewünscht ist auf alle Fälle notwendig:

Zitat:

Für alle $\begin{align*} r \end{align*}$ mit $\begin{align*} 1\leq r\leq n \end{align*}$ sowie alle $\begin{align*} r \end{align*}$ -Tupel $\begin{align*} (j_1,\ldots,j_r) \end{align*}$ mit $\begin{align*} 1\leq j_1<j_2<\ldots<j_r\leq n \end{align*}$ muss gelten

$\begin{align*} \left| A_{j_1} \cup A_{j_2} \cup \ldots \cup A_{j_r} \right| \geq r\cdot k \end{align*}$ (*).

Wieso ist das notwendig? Nun, angenommen, es gibt ein $\begin{align*} r \end{align*}$ und zugehöriges $\begin{align*} r \end{align*}$ -Tupel $\begin{align*} (j_1,\ldots,j_r) \end{align*}$ mit $\begin{align*} \left| A_{j_1} \cup A_{j_2} \cup \ldots \cup A_{j_r} \right| < r\cdot k \end{align*}$ .

Die $\begin{align*} r\cdot k \end{align*}$ notwendigen Zeilen für die Spalten $\begin{align*} j_1,\ldots,j_r \end{align*}$ können sich aber nur aus der Vereinigung $\begin{align*} A_{j_1} \cup A_{j_2} \cup \ldots \cup A_{j_r} \end{align*}$ bedienen, denn alle anderen Zeilen besitzen in diesen $\begin{align*} r \end{align*}$ Spalten ausschließlich Nullen. Und wie man sieht, ist die Vereinigung schlicht zu klein, um alle $\begin{align*} r\cdot k \end{align*}$ Zeilen zu liefern.

Bleibt die Frage, ob (*) auch hinreichend ist. verwirrt

In deinem Fall oben wären das übrigens

$\begin{align*} A_1 = \{1,4,5,8,9\},\; A_2=\{2,4,5,6,9\},\; A_3=\{2,3,5,7,8\} \end{align*}$ ,

und die Überprüfungen des Kriteriums ergeben

r=1 : $\begin{align*} |A_1| = 5,\; |A_2|=5,\; |A_3|=5 \end{align*}$ , sämtlich >3

r=2 : $\begin{align*} |A_1\cup A_2| = 7,\; |A_1\cup A_3|=8,\; |A_2\cup A_3|=8 \end{align*}$ , sämtlich >6

r=3: $\begin{align*} |A_1\cup A_2\cup A_3|=9 \end{align*}$ .

P.S.: Die angesprochenen Nullzeilen würden übrigens den Teil $\begin{align*} r=n \end{align*}$ dieses Kriteriums verletzen.

09.10.2017, 17:34

vonluetzen

Auf diesen Beitrag antworten »

Hallo Hal 9000,

die Bedingung macht Sinn. Ich denke aber nicht, dass diese hinreichend ist. Die Frage ist auch wenn es eine Lösung gibt, wie kann ich diese ermitteln? Hast du eine Idee wie ich vielleicht iterativ die Gruppen bilden könnte?

VG

09.10.2017, 17:47

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von vonluetzen
Ich denke aber nicht, dass diese hinreichend ist.

Kannst du das belegen durch ein Beispiel? D.h., eins, wo diese Bedingung erfüllt ist, aber dennoch keine Aufteilung möglich ist? Das würde mir ein wenig auf die Sprünge helfen, denn momentan habe ich den (allerdings noch unbewiesenen) Verdacht, dass es doch hinreichend ist.

10.10.2017, 09:26

vonluetzen

Auf diesen Beitrag antworten »

Hallo Hal 9000,

sorry ich habe dein Kriterium erst jetzt voll verstanden. Ich konnte gestern tatsächlich kein Gegenbeispiel finden.

Frage ist jetzt wie ich eine Ordnung herstellen kann, wenn diese Bedingung erfüllt ist. Was hältst du von meinem Lösungsansatz? Wie könnte ich diesen fortführen?

Danke für deine Hilfe!

VG

Neue Frage »

Antworten »

Reihen einer Matrix (n,m) nach Bedingungen in Gruppen sortieren

Verwandte Themen