4. kombinatorik

kombinatorik

  • Mod

    Damit das eben schnell vom Tisch ist, hier eine systematische Lösung:

    #include <iostream>
#include <vector>
#include <string>

using namespace std;

void combinator(vector<vector<string> > word_groups, string combination = "")
{
  cout << combination << '\n';
  for (unsigned group_index = 0; group_index < word_groups.size(); ++group_index)
    {
      for(unsigned word_index = 0; word_index < word_groups[group_index].size(); ++word_index)
        {
          string new_combination = combination + word_groups[group_index][word_index];
          vector<vector<string> > remaining_words = word_groups;
          remaining_words[group_index].erase(remaining_words[group_index].begin() + word_index, remaining_words[group_index].end());
          combinator(remaining_words, new_combination);
        }
    }
}

int main()
{
  combinator({{"A3", "A2", "A1"}, {"B3", "B2", "B1"}});
}

    Die Ausgabe spare ich mir mal, da ewig lang.

    Weiterhin ist eine Möglichkeit bei der Zufallskombinationserzeugung, um alle Kombinationen mit der gleichen Wahrscheinlichkeit zu ziehen, die gute alte Wegwerfmethode: Wir ziehen eine Kombination aus dem Raum aller möglichen Kombinationen der vorhanden Elemente, ohne Beachtung der Nebenbedingungen über die Reihenfolge. Das kann man leicht hinbekommen, dass diese gleichverteilt sind. Dann testen wir, ob die Nebenbedingungen erfüllt sind. Falls ja: Angenommen. Falls nein: Noch einmal von vorne. So bekommen wir gleichverteilt gültige Kombinationen. Das Problem ist, dass die Methode sehr ineffizient sein kann, wenn man viel wegwerfen muss. Hier wissen wir schon, dass wir im {3,3}-Fall nur 244 Treffer pro 720 Versuchen erwarten können. Bei großen Alphabeten wird das Verhältnis immer schlimmer.
    Es juckt mich zwar in den Fingern, nun ein Programm zu schreiben, das anhand dieser Methode versucht die Anzahl der möglichen Kombinationen zu schätzen, indem man das Geburtstagsparadoxon umkehrt. Aber erstens habe ich gerade keine Zeit dafür und zweitens steht anhand obiger Überlegung über die Wegwerfmethode jetzt schon so gut wie fest, dass die Methode viel ineffizienter wäre als das systematische Zählen. Und man bekommt nicht einmal ein genaues Ergebnis, sondern nur eine Schätzung.

    0
  • V

    SeppJ schrieb:

    Kann ich nicht nachvollziehen, denn die Mathematik sagt doch, dass zum reinen Zählen der Kombinationen der Zufall ungeeignet ist.

    Deine vielleicht. Meine kann mir recht glaubwürdig aufdecken, wieviele Seiten ein Würfel hat, wenn ich 100-mal würfle und die Ergebnisse in einer unordered_map sammle. Ok, man braucht VIELE Schleifendurchläufe, wenn ich mich recht erinnere, hatte maxxi nur 244 statt Deiner 245 raus.

    SeppJ schrieb:

    Damit das eben schnell vom Tisch ist, hier eine systematische Lösung:

    Uih, ist die kurz. Chapeau!
    Mal schauen, ob ich sie verstehe.

    Ausgabe von SeppJ(2,2):

    A2
A2B2
A2B1
A2B1B2
A1
A1A2
A1A2B2
A1A2B1
A1A2B1B2
A1B2
A1B2A2
A1B1
A1B1A2
A1B1A2B2
A1B1B2
A1B1B2A2
B2
B2A2
B2A1
B2A1A2
B1
B1A2
B1A2B2
B1A1
B1A1A2
B1A1A2B2
B1A1B2
B1A1B2A2
B1B2
B1B2A2
B1B2A1
B1B2A1A2

    Ausgabe von SeppJ(2,2)|sort:

    A1
A1A2
A1A2B1
A1A2B1B2
A1A2B2
A1B1
A1B1A2
A1B1A2B2
A1B1B2
A1B1B2A2
A1B2
A1B2A2
A2
A2B1
A2B1B2
A2B2
B1
B1A1
B1A1A2
B1A1A2B2
B1A1B2
B1A1B2A2
B1A2
B1A2B2
B1B2
B1B2A1
B1B2A1A2
B1B2A2
B2
B2A1
B2A1A2
B2A2

    Jo, das erscheint mir glaubwürdig.

    Der leere String ist noch dabei, das ist auch gut so für die EOIS, man zählt ja auch immer die leere Teilmnenge mit und so. *patsch*, naklar hat maxxi deshalb eins weniger.

    Das Ergebnis ist…
    (*Trommelwirbel*)
    https://oeis.org/A084771
    …Tataa!

    Ich fall vom Stuhl. Das ist mir wirr.

    0
  • Mod

    Ich war mir nicht sicher, ob ich die leere Menge zählen soll. Beim Code auf Seite 1 zähle ich sie absichtlich nicht, beim Code auf Seite 2 aus Faulheit aber doch, da mir die Ausgabe am Anfang "natürlicher" scheint, als eine Ausgabe vor Verzweigung der Rekursion.

    Das Ergebnis ist…
    (*Trommelwirbel*)
    https://oeis.org/A084771
    …Tataa!

    Kopf-Tisch. Als ich auf Seite 1 verschiedene Zahlenkombinationen durch OEIS gejagt habe, hatte ich angenommen, dass OEIS mit off-by-1-Fehlern zurecht kommt. Dem ist anscheinend nicht so. Nicht, dass die Sache durch die gefundene Folge klarer wäre 😕 .

    Deine vielleicht. Meine kann mir recht glaubwürdig aufdecken, wieviele Seiten ein Würfel hat, wenn ich 100-mal würfle und die Ergebnisse in einer unordered_map sammle.

    Ich zähle zigfachen Aufwand eben als "ungeeignet" 🙂 . Die Systematik muss den Würfel schließlich nur 6x angucken.

    Mal schauen, ob ich sie verstehe.

    Ich hätte gedacht, dass du die Variante auf Seite 1 lieber magst, da sie wegabstrahiert, welche Buchstaben noch vorhanden sind, sondern nur beachtet, wie viele Buchstaben noch möglich sind, wenn man das Wort um 1 verlängert. Letztlich läuft sie natürlich genau so viele Wege ab wie die 2. Lösung, aber mit ein wenig mehr Aufwand könnte man schon bekannte Teillösungen irgendwo speichern und bräuchte dann nicht zigfach neu berechnen, wie viele Kombinationen hinzu kommen, wenn man noch (x,y)-Buchstaben übrig hat. So könnte man auch tatsächlich mal den (15,15)-Wert berechnen (was mit dem jetzigen Programm eine Weile dauern würde).

    0
  • Mod

    SeppJ schrieb:

    Ich hätte gedacht, dass du die Variante auf Seite 1 lieber magst, da sie wegabstrahiert, welche Buchstaben noch vorhanden sind, sondern nur beachtet, wie viele Buchstaben noch möglich sind, wenn man das Wort um 1 verlängert. Letztlich läuft sie natürlich genau so viele Wege ab wie die 2. Lösung, aber mit ein wenig mehr Aufwand könnte man schon bekannte Teillösungen irgendwo speichern und bräuchte dann nicht zigfach neu berechnen, wie viele Kombinationen hinzu kommen, wenn man noch (x,y)-Buchstaben übrig hat. So könnte man auch tatsächlich mal den (15,15)-Wert berechnen (was mit dem jetzigen Programm eine Weile dauern würde).

    Genau das habe ich übrigens mal gemacht. Die naive Lösung auf Seite 1 rechnet minutenlang (selbst wenn man den Code auf 2 Alphabete optimiert, anstatt eine beliebige Zahl zuzulassen), wenn man alle (x,y) Kombinationen von 0 bis 14 ausrechnet. Diese Lösung braucht nur Sekundenbruchteile:

    #include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdint>

using namespace std;

class TwoAlphabetCombinator // Leicht mit Templates verallgemeinerbar auf N Alphabete, aber ich will's nicht übertreiben
{
  unordered_map<uint32_t, unsigned long> known_num_combinations;
  uint32_t alphabet_size_mapper(uint16_t size1, uint16_t size2) {return (size1 << 16) | size2; }
  void submit_known_num_combinations(uint16_t size1, uint16_t size2, unsigned long num_combinations)
  {
    uint32_t index1 = alphabet_size_mapper(size1, size2);
    uint32_t index2 = alphabet_size_mapper(size2, size1);
    known_num_combinations.insert(make_pair(index1, num_combinations));
    known_num_combinations.insert(make_pair(index2, num_combinations));    
  }

  unsigned long lookup_known_num_combinations(uint16_t size1, uint16_t size2)
  {
    return known_num_combinations[alphabet_size_mapper(size1, size2)];
  }

public:
  unsigned long get_num_combinations(uint16_t alphabet_A_size, uint16_t alphabet_B_size)
  {
    unsigned long num_combinations = 0;
    for(unsigned character_index = 1; character_index <= alphabet_A_size; ++character_index)
      {
        num_combinations += 1;
        unsigned long known_num_combinations = lookup_known_num_combinations(alphabet_A_size - character_index, alphabet_B_size);
        if (!known_num_combinations)
          num_combinations += get_num_combinations(alphabet_A_size - character_index, alphabet_B_size);
        else
          num_combinations += known_num_combinations;
      }
    for(unsigned character_index = 1; character_index <= alphabet_B_size; ++character_index)
      {
        num_combinations += 1;
        unsigned long known_num_combinations = lookup_known_num_combinations(alphabet_A_size, alphabet_B_size - character_index);
        if (!known_num_combinations)
          num_combinations += get_num_combinations(alphabet_A_size, alphabet_B_size - character_index);
        else
          num_combinations += known_num_combinations;
      }
    submit_known_num_combinations(alphabet_A_size, alphabet_B_size, num_combinations);
    return num_combinations;
  }
};

int main()
{
  TwoAlphabetCombinator foo;
  for (int i = 0; i < 15; ++i)
    for(int j = 0; j < 15; ++j)
      {
        cout << i << ' ' << j << ' ' <<  foo.get_num_combinations(i,j) << '\n';
      }
}

    Und dies ist nur die allererste Implementierung. Ich habe nicht einmal begonnen, nach Mikrooptimierungen zu schauen. Ein paar Szenarien, die mir direkt einfallen:
    -Testen, ob unordered_map wirklich optimal ist
    -Testen, ob man vielleicht was machen kann bezüglich des Mappers
    -Testen, ob man vielleicht bei kleinen Größen lieber die Rekursion rechnen lässt, anstatt einen Lookup zu starten
    Aber da das Programm jetzt schon schneller ist als ein Mensch gucken kann, hat sich nichts davon gelohnt :p . Somit erhält man (nach zahlreichen Zwischenausgaben):

    14 14 3634723102112

    Ja, passt immer noch zu der OEIS-Folge (hier habe ich die leere Menge wieder weg gelassen).

    Man kann damit natürlich nicht mehr alle Kombinationen ausgeben, aber das würde wohl sowieso unrealistisch lange dauern, bei über 3 Billionen Kombinationen.

    PS: Dies ist jetzt aber wirklich der Zufallsmethode weit überlegen. Nicht nur ein Faktor 100, sondern eher 100 Größenordnungen 🙂 .

    0
  • J

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

    edit: die kanonisch DP-Implementierung sollte dann schon nochmal nen Tacken schneller sein, weil die ganzen Checks wegfallen was schon berechnet wurde. Das vorliegende Programm legt ja letztlich nur die Äste der Rekursion aufeinander.

    0
  • 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