4. kombinatorik

kombinatorik

  • Mod

    maxxi schrieb:

    hast du einen besseren algo?

    Systematisch alle Kombinationen durchgehen?

    Solch einen Zufallsansatz würde man machen, wenn man eine Funktion über einer sehr, sehr großen Grundmenge berechnen wollte. Aber hier ist das komplett kontraproduktiv, denn man möchte ja wissen, wie groß die Grundmenge überhaupt ist. Das heißt, es ist weder garantiert, dass man überhaupt den ganzen Raum erwischt und gerade in den interessanten Fällen (wenn es viele Möglichkeiten gibt) geht es sogar eher schief als in einfachen Fällen.

    0
  • V

    SeppJ schrieb:

    maxxi schrieb:

    hast du einen besseren algo?

    Systematisch alle Kombinationen durchgehen?

    Solch einen Zufallsansatz würde man machen, wenn man eine Funktion über einer sehr, sehr großen Grundmenge berechnen wollte. Aber hier ist das komplett kontraproduktiv, denn man möchte ja wissen, wie groß die Grundmenge überhaupt ist. Das heißt, es ist weder garantiert, dass man überhaupt den ganzen Raum erwischt und gerade in den interessanten Fällen (wenn es viele Möglichkeiten gibt) geht es sogar eher schief als in einfachen Fällen.

    Das ist ein gutes Vorgehen: Erstmal überhaupt Zahlen kriegen, die nicht völlig geraten sind. Um weitere Implementierungen testen zu künnen. Die nächste wäre vielleicht eine, die verdammig viele konstruiert und viel Junk wegwirft. Dann vielleicht eine, die nur Ham produziert. Dann eine, die nur zählt. Dann vielleicht ein wenig Rekursion einbauen oder wegmachen je was einfacher wird.

    Nee, der Zufallsweg ist schon ein starker Einstieg für einen Informatiker, der sich an der Mathematik übt. Ich überspringe ihn zwar gerade, aber auch nur, weil ich zehn Jahre Jester/SeppJ/Bashar und viele andere Größen lese, die bei sowas gerne ihren mathematischen Schwengel (im positiven Sinne, also erklärend und reduzierend) zeigen.

    0
  • Mod

    volkard schrieb:

    Nee, der Zufallsweg ist schon ein starker Einstieg für einen Informatiker, der sich an der Mathematik übt.

    Kann ich nicht nachvollziehen, denn die Mathematik sagt doch, dass zum reinen Zählen der Kombinationen der Zufall ungeeignet ist. Wenn wir hingegen so etwas heraus finden wollten, wie zum Beispiel der Anteil der Kombinationen, die ein bestimmtes Kriterium erfüllen (welcher Teil der Kombinationen hat A3 an vierter Stelle?) dann ist die Zufallsmethode gut, da sie auch mit einem richtig großen Alphabet* funktioniert (wo die systematische Methode sich totrechnet). Zumindest, wenn wir es so hinbekommen, dass wir alle möglichen Kombinationen gleich wahrscheinlich hinbekommen (oder anhand einer Kombination sagen können, wie wahrscheinlich wir gerade diese Kombination erzeugen würden). Das im letzten Satz beschriebene Problem ist nicht trivial, da dazu vermutlich das Ursprungsproblem gelöst werden muss, wie viele Kombinationen es zu welchem Alphabet gibt. Aber wenn man dieses Problem löst, dann kann man mit dem Zufall tolle Sachen effizient (und zwar viel effizienter als mit der systematischen Methode) ausrechnen. Mit diesem Wissen können wir dann sogar Berechnungen über die Gesamtzahl der Kombinationen anstellen (falls diese noch unbekannt sein sollte), indem wir die Kollisionswahrscheinlichkeit bei der Zufallserzeugung messen.

    *: Ich verwende in diesem Thread Alphabet und Wörterbuch inkonsistent. Was ist hier der korrekte informatische Jargon?
    {{A1, A2, A3}, {B1, B2, B3}} ist ein Alphabet oder ein Wörterbuch oder eine Menge von Alphabeten oder eine Menge von Wörterbüchern?
    A1 ist ein Buchstabe oder ein Wort (hier meine ich mit A1 nicht die einelementige Sequenz A1, sondern das Element aus der obigen Menge)?
    A1B2A2B3 ist ein Wort oder ein Satz?

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