[gelöst]Kombinatorik alle Möglichkeiten mit Wiederholung

mirrowwinger

Hallo c-community,

ich habe ein Problem. Ich wollte mir alle möglichen Kombinationen von den Zahlen 1..9 als String erstellen. Hierbei habe ich mich erstmal schlau gemacht und diese Formel gefunden:

Anzahl = (N + k -1)! / ((N - 1)! * k!)

Wobei N = Anzahl der Elemente (im vorliegenden Beispiel 9)
k = Anzahl der verwendeten Elemente (im vorliegenden Beispiel auch 9) sind.

Nach meinen Mathematikkenntnissen habe ich 24310 Kombinationen erhalten. Diese Wollte ich versuchsweise mal ausgeben und habe folgende Funktion (eigene Kreation) verwendet:

for (i = MinLength; i <= MaxLength; i++)
	{
		char* caFirstString = malloc(sizeof(char) * (i + 1));
		char* caLastString  = malloc(sizeof(char) * (i + 1));

		int j;
		for (j = 0; j < i; j++)
		{
			caFirstString[j] = CharSet[0];
			caLastString[j]  = CharSet[strlen(CharSet) - 1];
		}
		caFirstString[i] = '\0';
		caLastString[i]  = '\0';
		do
		{

			// Screening-Funktion jedes 10. ausgeben
            //if ((iCount % 10) == 0)	Screen(iCount, iSum, caFirstString);

            // Zählvariable
			iCount++;

			int iChange = 0;
			int iPos = strlen(caFirstString) - 1;
			do
			{
				char* caTmpString = malloc(sizeof(char));
				caTmpString[0]  = caFirstString[iPos];
				if (strcspn(CharSet, caTmpString) == (strlen(CharSet) -1))
				{
					iChange = 1;
					caFirstString[iPos] = CharSet[0];
					iPos--;
				}
				else
				{
					iChange = 0;
					caFirstString[iPos] = CharSet[strcspn(CharSet, caTmpString) + 1];
				}
				free(caTmpString);
			}
			while (iChange != 0);
		}
		while (strcmp(caFirstString, caLastString) != 0);

Ich habe für die oben angegebene Voraussetzung von 9 Elementen und 9 Varianten bei einem Counter-Stand von 185.000+ abgebrochen, was mehr als das 9 fache ist.

Ich stehe jetzt etwas auf dem Schlauch. Habe ich die falsche Formel verwendet oder einen Denkfehler in meiner Funktion?

Hoffe jemand kann mir hier kurz helfen. Eigentlich höhren sich lediglich 24310 Kombinationen für 9 Stellige Kombinationen, wo Wiederholung von Zeichen zugelassen sind, sehr wenig an. Aber ich habe diese Formel auf 2 Seiten (wiki und eine 2. unabhängige) gefunden.

MfG
mirrowwinger

Belli

mirrowwinger schrieb:

Ich wollte mir alle möglichen Kombinationen von den Zahlen 1..9 als String erstellen.

Also 123...
213...
231...
132...
312...
321...
?
Die Formel dafür ist für 9 Zeichen einfach 9!

mirrowwinger

@Belli

um dann einfach auf dein Beispiel zurück zu greifen mit 3 Zeichen:

3! = 1 * 2 * 3 = 6

Test:

1. 111
2. 112
3. 113
4. 121
5. 122
6. 123

Für dieses Beispiel gibt es von Hand 27 (falls ich mich nicht verzählt habe) Kombinationen.

Oder ich hab dich falsch verstanden.

Für die Formel aus meinem ersten Post scheint das aber auch nicht zu passen:

((3 + 3 - 1)! / (2! * 3!)) = (5! / (2! * 3!) = 120 / 12 = 10

Zwischen 27 und 10 ist auch ein deutlicher Unterschied.

[Edit1]Könnte folgende Formel stimmen?

Anzahl = pow(N,k);

Dies hat zumindest bei den kleineren Beispielen (4 Zeichen und 2 Elemente, 3 Zeichen und 3 Elemente, ...) übereinstimmungen mit der Auszählung!

mirrowwinger schrieb:

Für dieses Beispiel gibt es von Hand 27 (falls ich mich nicht verzählt habe) Kombinationen.

Richtig, das ist 3*3*3 = 3³ = 27

Du hast jetzt 9 Zeichen und 9 Stellen. Das sind dann 9⁹ = 387420489 Möglichkeiten

Wenn du nur zwei Zeichen hast (0 und 1) und 8 Stellen, dann sind das 2⁸ = 256 Möglichkeiten.
Bitte ein Byte.

mirrowwinger

Danke wiedermal, Problem gelöst. Auf in ein neues Abenteuer

Belli

Ich hatte Dich missverstanden. Mir war nicht klar, dass Du aus der Menge '1' ... '9' die Zeichen auch mehrfach einsetzen wolltest ...