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

[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