4. kombinatorik

kombinatorik

  • Mod

    Jester schrieb:

    Magst du vielleicht noch die passende Rekurrenz angeben der Vollständigkeit halber?

    Das sollte (für 2 Alphabete) folgendes sein (ungeprüft):
    a(n,m)=∑i=1n(1+a(n−i,m))+∑i=1m(1+a(n,m−1))a(n, m) = \sum_{i=1}^{n}\left(1 + a(n-i, m)\right) + \sum_{i=1}^{m}\left(1 + a(n, m - 1)\right)
    mit a(0, 0) = 0 (wenn man die leere Menge nicht zählt)

    die kanonisch DP-Implementierung sollte dann schon nochmal nen Tacken schneller sein, weil die ganzen Checks wegfallen was schon berechnet wurde.

    kanonische DP-Implementierung? Vermutlich kenne ich, was du meinst, aber der Begriff sagt mir nichts und finden tue ich zu dem Stichwort auch nichts.

    0
  • J

    Naja, halt ein 2D-Array und das Zeilenweise ausfüllen. Ich finde das ziemlich kanonisch.

    0
  • J

    Es sollte sich auch lohnen zwei zusätzliche Tabellen mitzuführen:

    b_1(n,m)=∑_i=1n(1+a(n−i,m))b\_1(n, m) = \sum\_{i=1}^{n}\left(1 + a(n-i, m)\right)

    b_2(n,m)=∑_i=1m(1+a(n,m−1))b\_2(n,m) = \sum\_{i=1}^{m}\left(1 + a(n, m - 1)\right)

    Dann wird das Update zu a(n,m)=b_1(n−1,m)+b_2(n,m−1)a(n,m) = b\_1(n-1,m) + b\_2(n,m-1)
    und b_1(n,m)=b_1(n−1,m)+a(n,m)+1;b_2(n,m)=b_2(n,m−1)+a(n,m)+1b\_1(n,m) = b\_1(n-1,m) + a(n,m)+1; \quad b\_2(n,m) = b\_2(n,m-1) + a(n,m)+1 oder so ähnlich (grad kein Papier da, aber das sollte sich schnell prüfen lassen). Damit dürfte die Laufzeit O(Produkt der Gruppengrößen) werden (bisher ist sie das Quadrat davon). Außerdem kann man den Speicherbedarf natürlich drücken indem man entlang der Diagonalen ausfällt und alte Einträge vergisst, auf die wegen der Hilfstabelle ohnehin nicht mehr zugegriffen wird. Damit würde man nur noch drei Arrays (mit Größen n,m und min{n,m}) haben, in denen man mehr oder weniger wild Werte rumgeschaufelt werden. 😃

    Einzig das Ausgeben der Werte gestaltet sich dann etwas unangenehmer -- geht aber überraschenderweise auch noch mit der speicherreduzierten Variante (Stichwort: Hirschberg's algorithm).

    0
  • Mod

    Jester schrieb:

    Naja, halt ein 2D-Array und das Zeilenweise ausfüllen. Ich finde das ziemlich kanonisch.

    Ich kann mit dem "DP" nichts anfangen, darauf bezog sich meine Bemerkung. Auch mit deiner Erklärung, was du meinst, weiß ich immer noch nicht, wofür das stehen soll. Differenzen Programm?

    0
  • J

    Naja, halt ein 2D-Array und das Zeilenweise ausfüllen. Ich finde das ziemlich kanonisch.

    0
  • N

    SeppJ schrieb:

    Ich kann mit dem "DP" nichts anfangen, darauf bezog sich meine Bemerkung. Auch mit deiner Erklärung, was du meinst, weiß ich immer noch nicht, wofür das stehen soll. Differenzen Programm?

    http://en.wikipedia.org/wiki/Dynamic_programming

    Siehe insbesondere "memoization" und so.

    0
  • J

    Ganz genau, oder zu deutsch "dynamische programmierung". Sorry mir war nicht klar nach was du genau gefragt hast. Und nachdem mein erstes Posting mehr oder weniger komplett unbeachtet blieb ging ich davon aus, dass ich da nur sachen geschrieben hatte, die ohnehin allen beteiligten klar waren.

    0
  • Mod

    Jester schrieb:

    Und nachdem mein erstes Posting mehr oder weniger komplett unbeachtet blieb ging ich davon aus, dass ich da nur sachen geschrieben hatte, die ohnehin allen beteiligten klar waren.

    Nein, das habe ich bewusst überlesen, da da in kompliziert formulierten Sätzen von irgendwelchen T und DP geredet wurde, ohne irgendeinen Hinweis, worum es überhaupt geht. Das war mir damals die Zeit zur Entschlüsselung nicht wert.

    Jetzt, wo du noch mal explizit auf den Beitrag aufmerksam machst ist klar, dass ich den hätte aufmerksamer lesen sollen.

    0
  • J

    Sind die Dinge jetzt im Nachimein klar(er) oder soll ich irgendwas davon nochmal genauer erklären? -- kann ich gerne machen. Nur zum Implementieren hab ich innerhalb der nächsten zwei Wochen voraussichtlich keine Zeit.

    0
  • Mod

    Nein, ist klar. Die Techniken sind mir durchaus bekannt. Ich habe nur nicht erkannt, wovon du sprichst, weil du Bezeichnungen wie selbstverständlich benutzt hast, die mir nicht geläufig waren.

    Da dem TE anscheinend das Interesse am Thread verloren gegangen ist (er wollte wohl wirklich nur die Zahl 244 wissen), werde ich aber davon absehen, das an diesem Beispiel konkret durchzuführen, außer er meldet sich nochmal.

    0
  • ?

    @Jester: kannst du die DP solution nochmal erklaeren?

    -maxxi

    0
Anmelden zum Antworten