3. Ideenlos bezüglich Algorithmus (Permutation)

Ideenlos bezüglich Algorithmus (Permutation)

  • ?

    Hallo zusammen,

    folgende Aufgabe habe ich zu lösen, wobei ich hier nicht nach fertigen Lösungen sondern nach einem Fingerzeig in die richtige Richtung frage.

    Gegeben ist eine 3 x 3 - Matrix A und die Mengen M_0 := { A, B, C, D }, M_1 := { 1, 2, 3, 4 } und M_2 := { a, b, c, d }.

    A ist nun mit Elementen aus den Mengen M_1, M_2, M_3 zu belegen, wobei eine Belegung als gültig erachtet wird, wenn:

    - Die Elemente aus M_0 auf den "Ecken" der Matrix liegen (also auf a_1,1 a_1,3 a_3,1 und a_3,3)
    - Das "innere" Element der Matrix (also a_2,2) mit einem Element aus M_2 gefüllt wird und
    - die restlichen, noch freien Plätze von Elementen aus M_1 belegt werden.

    Gültig wäre also beispielswiese:
    A 1 B
    2 a 3
    C 4 D

    Ein Program soll nun alle sinnvolle Belegungen ausspucken. Das ist zunächst kein Problem, aber es gibt die Forderung, dies rekursiv zu erledigen, und da fällt mir im Moment keine Lösung ein, zumindest keine, die ganzheitlich rekursiv ist.

    Ich habe mit einem ganz primitiven Permutationsalgorithmus (rekursiv!) mir für die Elemente aus M_1 und M_2 jeweils eine Liste aller Permutationen erstellt.
    Um alle Kombinatinoen zu erhalten, könnte ich nun so vorgehen:

    für alle a aus M_2:
  für alle p0 aus M_0_Permutationen:
    für alle p1 aus M_1_Permutationen:
      ausgabeKombination(a,m0,m1)

    Meines Erachtens hat es keinen Sinn, den Algorithmus nun in einen rekursiven umzuwandeln. Vermutlich ist mein Vorgehen, erst separat Permutationsliten rekursiv zu erstellen und DANN iterativ die Kombinationen zu legen, falsch.

    Wer hat eine Idee?

    0
  • C

    Du bildest die Permutationen ja per Backtracking, da kannst du doch gleich die gefundenen Elemente auf die Positionen verteilen und in der untersten Rekursionsebene das fertige Quadrat ausgeben.

    PS: Wenn ich mich nicht verrechnet habe, sind das 2304 Lösungen.

    0
  • N
    Mod

    Vielleicht hilft ein kleiner Blick auf den Arbeitsspeicher einer Möglichkeit ein wenig weiter:

    C:\Users\nachtfeuer>debug
-e210 "Aa4",24
-e220 "Bb3",24
-e230 "Cc2",24
-e240 "Dd1",24
-d 210
1E06:0210  41 61 34 24 00 00 00 00-00 00 00 00 00 00 00 00  Aa4$............
1E06:0220  42 62 33 24 00 00 00 00-00 00 00 00 00 00 00 00  Bb3$............
1E06:0230  43 63 32 24 00 00 00 00-00 00 00 00 00 00 00 00  Cc2$............
1E06:0240  44 64 31 24 00 00 00 00-00 00 00 00 00 00 00 00  Dd1$............
1E06:0250  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00  ................
1E06:0260  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00  ................
1E06:0270  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00  ................
1E06:0280  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00  ................
-

    Wenn ich richtig verstanden habe, kann man 4Kawumm mal 4Kawumm mal 4Kawumm rechnen, da kommen dann aber viel mehr Möglichkeiten raus.

    0
  • C

    nachtfeuer schrieb:

    Wenn ich richtig verstanden habe, kann man 4Kawumm mal 4Kawumm mal 4Kawumm rechnen, da kommen dann aber viel mehr Möglichkeiten raus.

    Was ist den "4Kawumm"? Wenn du damit die Fakultät meinst: Von der letzten Gruppe wird ja nur ein Element ausgewählt, da ist es egal, wie die übrigen drei permutiert sind.

    0
  • ?

    Hi,

    danke für die bisherigen Antworten.
    Also auch meines Erachtens müssten es definitiv 4! * 4! * 4 = 2304 sein.

    @CStoll: über deinen Vorschlag muss ich nochmal nachdenken 🙂

    0
  • M

    Edit: Verlesen.

    0
  • N
    Mod

    ach so, ich seh schon, ich habe die Fragen mit den Ecken falsch verstanden, geordnete Speicheransicht wohl eher so:

    1E06:0200  41 34 42 24 00 00 00 00-00 00 00 00 00 00 00 00  A4B$............
1E06:0210  31 62 32 24 00 00 00 00-00 00 00 00 00 00 00 00  1b2$............
1E06:0220  43 33 44 24 00 00 00 00-00 00 00 00 00 00 00 00  C3D$............

    wäre ja auch zu schön gewesen 😉
    kawumm meint Fakultät!

    0
  • ?

    @CStoll:

    dein Vorschlag leuchtet mir nich so ein, um genauer zu sein, weiß ich nicht so rehct, wie ich ihn umsetzen soll.

    Es ist schon richtig, dass ich die neuen Permutationen, die ich rekursiv berechne, direkt in das Quadrat setzen kann. Allerdings habe ich ja nicht nur eine "lokale" Permutation (die von M_0 beispielsweise) sondern eine "globale" Permutation (die Kombination von M_0 und M_1). Ich kann ja eine mögliche Kombination von Elementen aus M_0 ja für jede Kombination aus M_1 nochmal legen. Mir fällt es schwer, das Zusammenspiel der Mengen in einer einzigen rekursiven Methode zu implementieren.

    0
  • C

    Entweder du verwendest für jede Gruppe eine eigene "finde alle Permutationen"-Funktion, die sich dann auf der untersten Rekursionsebene gegenseitig aufrufen (d.h. wenn du eine komplette Permutation von M_0 hat, suchst du als nächstes alle Permutationen von M_1) oder du baust packst alle Sequenzen in ein Array und bildest dann eine abschnittsweise Permutation:

    void permute(int pos, int max, char* werte, char* permutiert, int seqlen)
{
  if(pos==max)
    ausgabe(permutiert);
  int seqstart = (pos/seqlen)*seqlen;
  int seqend = seqstart+sqlen;
  for(int index=seqstart;index<seqend;++index)
    if(find(permutiert,permutiert+pos,werte[index])==permutiert+pos)
    {
      permutiert[pos] = werte[index];
      permute(pos+1,max,werte,permutiert,seqlen)
    }
}

char s[]="ABCD1234abcd";
char p[sizeof(s)];
permute(0,9,s,p,4);

    (ungetestet und aus dem Stegreif hingeschrieben)

    0
  • ?

    Hi CStoll,

    ich habe mein Problem jetzt so gelöst, wie du es zuerst vorgeschlagen hast: dass ich in der letzten Rekursionsstufe, wenn eine Kombination gelegt wurde, die Rekursion für alle Permutationen der zweiten Menge aufrufe.

    Vielen Dank für die kompetente Hilfe, Herr Dipl. Inf. 🙂

    0
Anmelden zum Antworten