4. kombinatorik

kombinatorik

  • ?

    Hallo,

    ich habe folgende strings:
    A1,A2,A3,B1,B2,B3

    wie viele moeglichkeiten gibt es um diese zu kombinieren, wenn min length = 1 und max length = 6 sein darf wobei die reihenfolge (A2 folgt auf A1, bzw. B2 folgt auf B2) nicht vertauscht werden darf!?

    e.g.:
    Moeglichkeit 1: A1
    Moeglichkeit 2: B1
    Moeglichkeit 3: A1,B1,B2,A2,A3

    -Maxi

    0
  • ?

    meine ueberlegung:

    Position 1: 6 Moeglichkeiten (A1,A2,A3,B1,B2,B3)
    Position 2: 5 Moeglichkeiten (A2,A3,B1,B2,B3)
    Position 3: 4 Moeglichkeiten (A3,B1,B2,B3)
    Position 4: 3 Moeglichkeiten (B1,B2,B3)
    Position 5: 2 Moeglichkeiten (B2,B3)
    Position 6: 1 Moeglichkeiten (B3)

    6*5*4*3*2*1 = 720 dann noch * 2 weil ich mit B1 beginnen kann?

    -Maxi

    0
  • Mod

    Deine Überlegung lässt größtenteils außer Betracht, dass gewisse Elemente nicht auf andere folgen können, sowie dass die Länge nicht unbedingt 6 sein muss. Ich habe gerade nicht die Zeit, das Problem komplett durchzudenken (in ein paar Stunden habe ich vielleicht Zeit dafür), aber deine Überlegung ist offensichtlich falsch.

    Falls es wirklich nur um dieses eine Alphabet geht und nicht um tiefergehende Erkenntnisse (also das Aufstellen einer allgemeine Formel als Funktion der Wörtergruppen und Anzahl der Wörter in den Gruppen), dann kann man das auch mal eben fix Brute Forcen. Ein Programm dafür zu schreiben sollte Minutenaufwand sein, der Rechenaufwand im Sekundenbruchteilbereich.

    0
  • V

    SeppJ schrieb:

    dann kann man das auch mal eben fix Brute Forcen. Ein Programm dafür zu schreiben sollte Minutenaufwand sein, der Rechenaufwand im Sekundenbruchteilbereich.

    Mit verschiedenen Eingabegrößen und dann in der OEIS nach der Formel schauen.

    0
  • Mod

    volkard schrieb:

    SeppJ schrieb:

    dann kann man das auch mal eben fix Brute Forcen. Ein Programm dafür zu schreiben sollte Minutenaufwand sein, der Rechenaufwand im Sekundenbruchteilbereich.

    Mit verschiedenen Eingabegrößen und dann in der OEIS nach der Formel schauen.

    Genau. Gesagt, getan:

    #include <iostream>
#include <vector>

using namespace std;

void combinator(vector<unsigned int> word_groups, unsigned &num_combinations)
{
  for (unsigned group_index = 0; group_index < word_groups.size(); ++group_index)
    {
      for(unsigned word_index = 1; word_index <= word_groups[group_index]; ++word_index)
        {
          num_combinations += 1;
          vector<unsigned int> remaining_words = word_groups;
          remaining_words[group_index] -= word_index;
          combinator(remaining_words, num_combinations);
        }
    }
}

int main()
{
  /*  cout << "One group combinations:\n";
      for (unsigned i = 1; i < 20; ++i)
      {
      unsigned num_combinations = 0;
      vector<unsigned> word_groups = {i};
      combinator(word_groups, num_combinations);
      cout << num_combinations << ',';
      }
      cout << '\n';*/
  cout << "Two group combinations:\n";
  for (unsigned i = 1; i < 10; ++i)
    {
      for (unsigned j = 1; j < 10; ++j)
        {
          unsigned num_combinations = 0;
          vector<unsigned> word_groups = {i, j};
          combinator(word_groups, num_combinations);
          cout << i<< ',' << j<< ": " << num_combinations << '\n';
        }
      cout << '\n';
    }
}

    Eine Wortgruppe der Größe N gibt Ergebnisse:

    1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287

    Ja, macht Sinn. Für eine Wortgruppeist das Programm korrekt.
    Für zwei Wortgruppen, der Größen N und M (N zuerst, dann M):

    1,1: 4
1,2: 11
1,3: 27
1,4: 63
1,5: 143

2,1: 11
2,2: 32
2,3: 85
2,4: 215
2,5: 527

3,1: 27
3,2: 85
3,3: 244
3,4: 663
3,5: 1735

4,1: 63
4,2: 215
4,3: 663
4,4: 1920
4,5: 5321

5,1: 143
5,2: 527
5,3: 1735
5,4: 5321
5,5: 15524

    Prüfen von Hand: Passt für 1,1. Passt für 1,2. Passt für 2,1. Für mehr reicht der Restplatz auf meinem Papier nicht mehr und außerdem dauert es mir zu lange. Mit der erfolgreichen Prüfung für kleine Werte und dem Vertrauen in meine Programmierkunst, erkläre ich das Programm für korrekt. Man sieht hier schon das Ergebnis für die konkrete frage des TE: 244. Passt auch grob vom Gefühl her, denn es muss deutlich weniger sein als 720, aber es müssen auch deutlich über 100 sein.

    Die (1, 😵 Werte sind laut OEIS:

    Main diagonal of the array defined by: T(0, j)=j+1 j>=0, T(i, 0)=i+1 i>=0, T(i, j)=T(i-1, j-1)+T(i-1, j)+1. a(n)=(n+4)*2^(n-1)-1.

    Beziehungsweise gleichbedeutend:

    a(0)=1, a(1)=4, a(2)=11, a(n) = 5*a(n-1)-8*a(n-2)+4*a(n-3).

    Das bestätigt sich auch, wenn ich die Reihe zu größeren X fortsetze. Die Formel sieht irgendwie kombinatorisch aus, aber es macht jetzt nicht wirklich 💡 bei mir.

    Andere Sequenzen ((2, 😵 usw.) geben kein Ergebnis bei OEIS. Ebenso die Diagonale. Sieht jemand durch Draufgucken ein Muster?

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