4. kombinatorik

kombinatorik

  • J

    Ich glaube T[i,j] ist die Anzahl der Wörter in denen in der ersten Gruppe bis höchstens zum i-ten und in der zweiten Gruppe bis höchstens zum j-ten Zeichen gegangen wurde. Dann gilt offensichtlich T[i,0]=i+1 und T[0,j]=j+1 (zumindest wenn man das leere Wort erlaubt).

    Allerdings würde ich bei der Komposition sowas erwarten wie
    T[i,j] = T[i-1,j] + T[i,j-1] - T[i-1,j-1] (das sind im wesentlichen alle Wörter, die die in einer der Gruppen ein Zeichen weniger benutzen, allerdings zählen wir so die Wörter doppelt, die in beiden Gruppen weniger Zeichen benutzen... also ziehen wir die einmal ab. Es kann gut sein, dass diese Rekurrenz dieselbe Lösung hat--hat jemand zeit und lust das rauszufinden?

    Mit der Methode sollte man auch ein DP bekommen, das das in Zeit O(NM) (allgemein O(Produkt der Gruppengrößen)) ausrechnet. Im zweifel würde ich dafür aber lieber mit T[i,j]=#Wörter, die genau i Zeichen aus Gruppe 1 und genau j Zeichen aus Gruppe 2 benutzen, ansetzen. Das macht die Rekurrenz offensichtlcih und man muss am achluss halt noch aufsummieren um alles zu bekommen.

    0
  • ?

    Hallo SeppJ,

    danke für die Hilfe.

    wie kann ich alle Kombinationen ausgeben? e.g. A1A2A3B1B2B3

    -Maxxi

    0
  • Mod

    maxxi schrieb:

    wie kann ich alle Kombinationen ausgeben? e.g. A1A2A3B1B2B3

    Mein Programm ist trickreich. Es erzeugt die Kombinationen nicht, es zählt nur, wie viele Knoten in einem Ast der Rekursion wären, indem es Buch führt, wie viele gültige Wörter noch vorhanden sind, aber nicht, welche. Ein Programm, das alle Kombinationen wirklich erzeugt, wäre ähnlich aufgebaut, rekursiv eben, aber eine Erweiterung meines jetzigen Programms wäre eher ein Hack. Kannst du programmieren? Sollte nicht schwer sein. Man müsste eben statt der Anzahl der verbleibenden Worte konkret die verbleibenden Worte mit herumschleppen, sowie eine Zeichenkette, um die aktuelle Kombination zu speichern.

    Ich habe leider für mindestens die nächsten 10 Stunden keine Zeit dafür.

    0
  • ?

    meine berechnung ergibt: 106

    ich versuche die kombinationen randomly zu berechnen und füge die ergebnisse in ein hashset ein...wenn ich genuegend iterationen durchlaufe, bekomme ich alle kombinationen...

    #include <unordered_set>
#include <sstream>
#include <string>
#include <iostream>
using namespace std;

const int seqLenMax = 3;
const unsigned long iterations = 5000000;
const int numberOfGroups = 2;

unsigned int getRandNum(unsigned int min, unsigned int max) {
   return rand() % (max + 1 - min) + min;
}

string intToString(unsigned int num) {
	stringstream ss;
	ss << num;
	string s = ss.str();
	return s;
}

string makeGroupString(string s, unsigned int num) {
	return s + intToString(num);
}

string generateRandSubSeq(unsigned int &seqLen1Min, unsigned int &seqLen2Min) {
	unsigned int selector = getRandNum(0, numberOfGroups - 1);
	string s;

	switch (selector) {
	case 0: 
		if (seqLen1Min <= seqLenMax) {
			unsigned int r = getRandNum(seqLen1Min, seqLenMax);
			s = makeGroupString("A", r);
			seqLen1Min = r + 1;
		}
		break;

	case 1:
		if (seqLen2Min <= seqLenMax) {
			unsigned int r = getRandNum(seqLen2Min, seqLenMax);
			s = makeGroupString("B", r);
			seqLen2Min = r + 1;
		}
		break;
	}

	return s;
}

int main() {
	unordered_set<string> hs;

	srand(time(NULL));

	for (unsigned long i = 0; i <= iterations; i++) {
		string subseq = "";
		unsigned int seqLen1Min = 1;
		unsigned int seqLen2Min = 1;

		while(true) {
			string s = generateRandSubSeq(seqLen1Min, seqLen2Min);

			if (seqLen1Min > seqLenMax && seqLen2Min > seqLenMax) {
				break;
			}

			subseq += s;
		}

		if (subseq.length() > 0) {
			hs.insert(subseq);
		}
	}

	for(auto k : hs) {
		cout << k << endl;
	}

	cout << "size: " << hs.size() << endl;
}
    0
  • V

    maxx schrieb:

    ich versuche die kombinationen randomly zu berechnen und füge die ergebnisse in ein hashset ein...wenn ich genuegend iterationen durchlaufe, bekomme ich alle kombinationen...

    Danke für den Code. Das spart viel Zeit bei eigenen Überlegungen.

    maxxi schrieb:

    meine berechnung ergibt: 106

    Habe mal unordered_set ersetzt durch set.
    Wo sind die Ketten
    A1
    A1A2A3B1B2B3
    B3A3
    ?
    Oder habe ich die Aufgabe falsch verstanden?

    (Ich würde für sowas ausnahmsweise den mersenne twister benutzen, damit man auf keinen Fall zufällig in einen Pseudozufallskreis fällt, aber das wird nicht so viele Fälle verschlucken.)

    maxxi schrieb:

    wobei die reihenfolge (A2 folgt auf A1, bzw. B2 folgt auf B2) nicht vertauscht werden darf!?

    Ähm, was soll hier "B2 folgt auf B2" bedeuten? Es spielen wohl maum zwei B2 mit. Ich las es als "B2 steht nicht vor B1".

    0
  • ?

    @volkard:
    da scheint noch ein bug im code zu sein...

    wobei die reihenfolge (A2 folgt auf A1, bzw. B2 folgt auf B2) nicht vertauscht werden darf!?

    das soll heisen:
    - die reihenfolge von Ax, wobei x eine zahl von 1-3 ist darf nur ansteigend sein
    - die reihenfolge von Bx, wobei x eine zahl von 1-3 ist darf nur ansteigend sein

    -maxx

    0
  • ?

    nun sinds 244...stimmt das?

    #include <set>
#include <sstream>
#include <string>
#include <iostream>
using namespace std;

const int seqLenMax = 3;
const unsigned long iterations = 5000000;
const int numberOfGroups = 2;

unsigned int getRandNum(unsigned int min, unsigned int max) {
   return rand() % (max + 1 - min) + min;
}

string intToString(unsigned int num) {
	stringstream ss;
	ss << num;
	string s = ss.str();
	return s;
}

string makeGroupString(string s, unsigned int num) {
	return s + intToString(num);
}

string generateRandSubSeq(unsigned int &seqLen1Min, unsigned int &seqLen2Min) {
	unsigned int selector = getRandNum(0, numberOfGroups - 1);
	string s;

	switch (selector) {
	case 0: 
		if (seqLen1Min <= seqLenMax) {
			unsigned int r = getRandNum(seqLen1Min, seqLenMax+1);
			if (r <= seqLenMax) {
				s = makeGroupString("A", r);
			}
			seqLen1Min = r + 1;
		}
		break;

	case 1:
		if (seqLen2Min <= seqLenMax) {
			unsigned int r = getRandNum(seqLen2Min, seqLenMax+1);
			if (r <= seqLenMax) {
				s = makeGroupString("B", r);
			}
			seqLen2Min = r + 1;
		}
		break;
	}

	return s;
}

int main() {
	set<string> hs;

	for (unsigned long i = 0; i < iterations; i++) {
		string subseq = "";
		unsigned int seqLen1Min = 1;
		unsigned int seqLen2Min = 1;

		while(true) {
			string s = generateRandSubSeq(seqLen1Min, seqLen2Min);

			subseq += s;

			if (seqLen1Min > seqLenMax && seqLen2Min > seqLenMax) {
				break;
			}			
		}

		if (subseq.length() > 0) {
			hs.insert(subseq);
		}
	}

	for(auto k : hs) {
		cout << k << endl;
	}

	cout << "size: " << hs.size() << endl;
}
    0
  • Mod

    maxxi schrieb:

    nun sinds 244...stimmt das?

    Lies den Thread.

    Wobei ich noch anmerken würde, dass ich geradezu bestürzt bin über die Idee, hier einen Zufallsgenerator zu benutzen.

    0
  • ?

    @SeppJ:
    ich sag ja nicht das der algo super ist, aber man kann ihn auf die schnelle mal runterschreiben 🙂
    hast du einen besseren algo?

    0
  • 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
Anmelden zum Antworten