Ansatz: Mengen, Relationen, Permutationen (oder sowas ähnliches)

[Wolf]

Guten Tag,

ich bin absoluter Programmieranfänger, bin allerdings gerade gezwungen es zu Nutzen und hoffe das jemand eine Idee zu meinem Problem hat.

Die Sprache: PHP (bin ich am wenigsten mies xD)

Problem:

Ich habe zwei n-Mengen, A und B, die jeweils die Zahlen 1 bis n enthalten und eine bestimmte Relation von A und B die ich ebenfalls eingebe.

Beispiel:
A = {1, 2, 3, 4, 5, 6}
B = {1, 2, 3, 4, 5, 6}

Und eine Relation die sich je nach Eingabe ändert.

Momentan habe ich:
A x B = {(1,2),(1,3),(1,4),(2,3),(2,5),(2,6),(3,4),(3,5),(4,2),(4,6),(5,1),(5,4),(5,6),(6,1),(6,3)}

Die 1 aus Menge A ist also der 2, 3 und 4 aus Menge B zugeordnet.

Jetzt suche ich alle Möglichkeiten wie man eine eindeutige Zuordnung aus der Menge AxB bekommt.

Hat da jemand eine Idee wie ich ansetzen könnte?

MfG Wolf

[ChrisB]

Hi,

Jetzt suche ich alle Möglichkeiten wie man eine eindeutige Zuordnung aus der Menge AxB bekommt.

Eindeutige Zuordnung von was zu was?

Willst du alle möglichen Tupel? Dann verstehe ich aber nicht, welchen Sinn das ergeben soll, wenn die Relation doch vorgegeben ist.

MfG ChrisB

[Wolf]

Eindeutige Zuordnung von was zu was?

Willst du alle möglichen Tupel? Dann verstehe ich aber nicht, welchen Sinn das ergeben soll, wenn die Relation doch vorgegeben ist.

Ich suche alle Möglichkeiten eine bijektive Zuordnung zu finden.

z.B. das sowas rauskommt wie:

C = {(1,3), (2,1), (3,4), (4,5), (5,6), (6,2)}

Also das jedes Element aus A GENAU EINEM Element aus B zugeordnet ist. Dafür gibt es bei der gegebenen Menge AxB mehrere Möglichkeiten und die Suche ich.

LG Wolf

[bleicher]

Grüße,
wo stammen die relationen her? kannst du uns etwas mehr verraten?
MFG
bleicher

[Wolf]

Grüße,
wo stammen die relationen her? kannst du uns etwas mehr verraten?
MFG
bleicher

Sicher,

ich habe einen vollständigen, gerichteten Graphen ohne Hebungen und Senkungen und die AxB-Menge ist eine andere Darstellung für die Adjazenzmatrix.

Vollständig := Jeder Knoten ist mit jedem anderen Knoten verbunden
Gerichtet := Jede Kante hat eine Richtung
Hebung := Zu einem Knoten gehen nur Kanten hin
Senkung := Von einem Knoten gehen nur Kanten weg

Ein Element aus meiner AxB-Menge, z.B. (1,2), heißt somit: Es existiert eine Kante die von Knoten 1 zu Knoten 2 geht.

Da durch die Vollständigkeit jeder Knoten mit jedem Vebunden ist, gibt es also z.B. (1,3) und (1,4), aber da die Kanten gerichtet kein (4,1) oder (3,1).

Ich suche jetzt die Hamiltonkreise in so einem Graphen. Für 4, 5, 6-Ecke ist es recht leicht, aber für 15-16 Ecke bekommt man da Probleme.

Zum Programmierproblem:
Habe jetzt einen Ansatz, der allerdings sehr statisch ist. Hier das was ich habe für die kleine Tabelle {(1,2),(1,3),(1,4),(2,3),(2,5)}, die ich in eine mysql-Tabelle geschrieben habe.

$result = mysql_query("SELECT * FROM save");  
$numrows = mysql_num_rows($result);  
$n = mysql_result($result, $numrows-1);  
$result1 = mysql_query("SELECT * FROM save WHERE A=1");  
$numrows1 = mysql_num_rows($result1);  
echo "Möglichkeiten = {";  
for($i=0; $i<$numrows1; $i++) {  
            $ausgabe1 = mysql_result($result1, $i, 'B');  
            $result2 = mysql_query("SELECT * FROM save WHERE A=2");  
            $numrows2 = mysql_num_rows($result2);  
            for($j=0; $j<$numrows2; $j++) {  
  
                      $ausgabe2 = mysql_result($result2, $j, 'B');  
                      $ausgabe = $ausgabe1.$ausgabe2;  
                      $text = "{".$ausgabe."}, ";  
                      if($ausgabe1 == $ausgabe2) { } else {   echo $text;     }  
                    }  
            }  
echo "}";

Mit der Ausgabe:
Möglichkeiten = {{23}, {25}, {35}, {43}, {45}}

Problem halt:
Wenn ich es so mache, klappt es wohl, aber ich muss das Programm immer anpassen, wenn ich das n ändere.

[Don P]

Hallo,

ich habe einen vollständigen, gerichteten Graphen ohne Hebungen und Senkungen und die AxB-Menge ist eine andere Darstellung für die Adjazenzmatrix.

Vollständig := Jeder Knoten ist mit jedem anderen Knoten verbunden
Gerichtet := Jede Kante hat eine Richtung
Hebung := Zu einem Knoten gehen nur Kanten hin
Senkung := Von einem Knoten gehen nur Kanten weg

Hier das was ich habe für die kleine Tabelle {(1,2),(1,3),(1,4),(2,3),(2,5)}

Das wären nur 5 Kanten in AxB?

Kann aber nicht sein, denn aus der geforderten Vollständigkeit folgt AFAIS, dass es insgesamt 1+2+3+...+(n-1) = n*(n-1)/2 Kanten geben muss.
Bei 5 Knoten sind es also 10 Kanten, nicht 5.

Oder gibst du nur einen Teil ein, und willst die anderen dann errechnen lassen?

Gruß, Don P

[Don P]

Hallo,

Für 6 Knoten schreibst du:

Momentan habe ich:
A x B = {(1,2),(1,3),(1,4),(2,3),(2,5),(2,6),(3,4),(3,5),(4,2),(4,6),(5,1),(5,4),(5,6),(6,1),(6,3)}

und suchst Lösungen, so dass

jedes Element aus A GENAU EINEM Element aus B zugeordnet ist.
Dafür gibt es bei der gegebenen Menge AxB mehrere Möglichkeiten.

Ja, aber die Ergebnismengen haben dann jeweils nur n Elemente ("jedes Element aus A GENAU EINEM Element aus B zugeordnet").

So langsam dämmert's mir:

Aus der gegebenen Menge AxB mit Mächtigkeit n*(n-1)/2 willst du also alle Teilmengen mit jeweils der Mächtigkeit n erstellen, bei denen "jedes Element aus A GENAU EINEM Element aus B zugeordnet ist". Die restlichen Kanten, die für die Vollständigkeit jeweils noch nötig wären, interessieren dich dann nicht mehr, richtig?

Da würde ich klein anfangen mit nur 3 oder 4 Knoten und einen *allgemeinen* Algorithmus suchen, der damit klar kommt. Sehr wahrscheinlich schafft er die Aufgabe dann auch mit mehr Knoten...

Gruß, Don P

[Don P]

Hallo,

Also:
Ich ordne 1->3 zu: (1,3)
Somit entfällt für 2: (2,3) und es bleiben (2,4) und (2,5).
Ich ordne 2->4 zu: (2,4)
Somit entfällt für 3: (3,4) und es bleibt (3,5)
Ich ordne 3->5 zu: (3,5).
usw.
und erhalte: C={ (1,3), (2,4), (3,5), ...}

Allerdings ist es möglich das eine vollständige Zuordnung nicht funktioniert, wenn ich am Anfang direkt 1->3 zuordne, sondern das ich mit 1->2 oder 1->4 hätte beginnen müssen.

Ich gehe mal davon aus, dass [1,1], [2,2] usw. keine möglichen Kanten sind, sonst stimmt auch meine Formel mit n*(n-1)/2 Kanten nicht.

Ob es klappt, hängt wohl davon ab, wieviele eingehende bzw. ausgehende Kanten es für einen Knoten gibt.

Nehmen wir deine Relation
A x B = {(1,2),(1,3),(1,4),(2,3),(2,5),(2,6),(3,4),(3,5),(4,2),(4,6),(5,1),(5,4),(5,6),(6,1),(6,3)}

Man könnte die ein-/ausgehenden Kanten erstmal Arrays anlegen und jedes sortieren:

A1 = [2,3,4]
A2 = [3,5,6]
A3 = [4,5]
A4 = [2,6]
A5 = [1,4,6]
A6 = [1,3]

Die erste Kante ist (1,2), wegen A*1* mit seinem ersten Element A1[0]=*2*. Man kann dann alle 2er aus den weiteren Arrays streichen, weil 2 als Ziel jetzt verbraucht ist.

Die zweite Kante ist (2,3), wegen A*2* mit seinem ersten Element A2[0]=*3*. Man kann dann alle 3er aus den weitern Arrays streichen.

Die dritte Kante ist (3,4), wegen A*3* mit seinem ersten Element A3[0]=*4*. Man kann dann alle 4er aus den weitern Arrays streichen.

Die vierte Kante ist (4,6), wegen A*4* mit seinem ersten Element A4[0]=*6* (die 2 wurde ja gestrichen). Man kann dann alle 6er aus den weitern Arrays streichen.

Die fünfte Kante ist (5,1), wegen A*5* mit seinem ersten Element A5[0]=*1*. Man kann dann den 1er aus dem letzten Array streichen.

Die sechste Kante ergibt sich nicht mehr, da A6 jetzt leer ist (1 und  3 wurden bereits gestrichen).

=> Mit (1,2) anfangen führt zu keinem Ergebnis.
Also weiter mit (1,3) etc., bis alle durch sind.

So etwa könnte ein allgemeiner Algorithmus aussehen.
Wie man das in PHP umsetzt, musst du selbst sehen: Ich würde JavaScript nehmen, weil ich da am wenigsten schlecht bin ;)

Man braucht dazu ein paar verschachtelte Scheifen. Statt Werte direkt aus den Arrays zu löschen kann man auch ein weiteres Array für verbrauchte Ziele benutzen und dann jeweils dort nachsehen, ob ein Wert dort schon vorhanden (also verbraucht) ist.

Gruß, Don P

[Vinzenz Mai]

Hallo,

Willst du alle möglichen Tupel? Dann verstehe ich aber nicht, welchen Sinn das ergeben soll, wenn die Relation doch vorgegeben ist.
Ich suche alle Möglichkeiten eine bijektive Zuordnung zu finden.

wovon

z.B. das sowas rauskommt wie:

C = {(1,3), (2,1), (3,4), (4,5), (5,6), (6,2)}

Also das jedes Element aus A GENAU EINEM Element aus B zugeordnet ist. Dafür gibt es bei der gegebenen Menge AxB mehrere Möglichkeiten und die Suche ich.

Schritt 1:

Alle möglichen bijektiven Zuordnungen, wenn die Reihenfolge der Tupel keine Rolle spielt und B gleichmächtig zu A ist, bekommst Du durch Ermitteln aller Permutationen der Elemente von B (was in Wirklichkeit ja ebenfalls A ist)

Ist n die Mächtigkeit von A, so hast Du n! Zuordnungen.

Schritt 2:

Spielt die Reihenfolge doch ein Rolle, so musst Du für jede Lösung aus A alle Permutationen der Tupel bilden. Da Du n Tupel hast, bekommst Du für jedes Element der Lösungsmenge aus Schritt 1 wiederum n! Zuordnungen, das wären insgesamt (n!)². Viel Spass beim Durchtesten.

Algorithmen zum Durchlaufen aller Permutationen einer n-elementigen Menge solltest Du über Deine bevorzugte Suchmaschine finden.

Freundliche Grüße

Vinzenz

[bleicher]

Grüße,

Hat da jemand eine Idee wie ich ansetzen könnte?

index des 2dimensionalen arrays?
index in einem eindimensionalen array der aus dem 2d geklebt ist?
MFG
bleicher

[Wolf]

index des 2dimensionalen arrays?
index in einem eindimensionalen array der aus dem 2d geklebt ist?

Was Arrays sind wird hier gut beschrieben und denk das ist klar, wenn ich es mir durchlese:
http://www.usegroup.de/software/phptutorial/arrays.html

Aber was stell ich damit an?

LG Wolf

[bleicher]

Grüße,

Aber was stell ich damit an?

array mit allen permutationen?
MFG
bleicher

[Wolf]

Grüße,

Aber was stell ich damit an?
array mit allen permutationen?
MFG
bleicher

Mh, nein. Ich brauche nicht alle Permutationen von A und B sondern die bijektiven Zuordnungen aus der Relation AxB.

Also:
Ich ordne 1->3 zu: (1,3)
Somit entfällt für 2: (2,3) und es bleiben (2,4) und (2,5).
Ich ordne 2->4 zu: (2,4)
Somit entfällt für 3: (3,4) und es bleibt (3,5)
Ich ordne 3->5 zu: (3,5).
usw.
und erhalte: C={ (1,3), (2,4), (3,5), ...}

Allerdings ist es möglich das eine vollständige Zuordnung nicht funktioniert, wenn ich am Anfang direkt 1->3 zuordne, sondern das ich mit 1->2 oder 1->4 hätte beginnen müssen.

Oder meinst du das?^^

LG ^^

[Gunnar Bittersmann]

@@Wolf:

nuqneH

Allerdings ist es möglich das eine vollständige Zuordnung nicht funktioniert, wenn ich am Anfang direkt 1->3 zuordne, sondern das ich mit 1->2 oder 1->4 hätte beginnen müssen.

Willst du diese dann auch haben oder nur alle Varianten, bei denen jedes Element aus A eine Zuordnung zu einem Element aus B hat?

Qapla'

[Wolf]

@@Wolf:

nuqneH

Allerdings ist es möglich das eine vollständige Zuordnung nicht funktioniert, wenn ich am Anfang direkt 1->3 zuordne, sondern das ich mit 1->2 oder 1->4 hätte beginnen müssen.

Willst du diese dann auch haben oder nur alle Varianten, bei denen jedes Element aus A eine Zuordnung zu einem Element aus B hat?

Qapla'

Es sollen nur die Varianten sein die wirklich vollständig sind. Wenn A kein Element in B mehr hat, dann kann das gestrichen werden.

LG Wolf