Laden...

Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets]

Erstellt von KRAFT vor 18 Jahren Letzter Beitrag vor 12 Jahren 28.565 Views
K
KRAFT Themenstarter:in
14 Beiträge seit 2005
vor 18 Jahren
Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets]

Hallo 🙂

Ich habe ein Schema mit 4 Feldern. Jedes dieser Felder kann einen von 3 Zustanden annehem (1,2,3). Die Anzahl der Möglichen Kombinatioen ist also 3 hoch 4 also 81 wenn ich das richtig sehe.

Um diese (alle) Kombinatioen zu erstellen (darzustellen) möchte ich eine Methode schreiben. Jetzt mal egal, wie ich das Designtechnisch mache.

Meine Überlegung war mehrere for-Schleifen in einander zu schachteln aber ... hat jemand so etwas eventuell schon einmal gemacht? Oder ist den Denkansatz falsch?
Wie hast du die "Zustände" dargestellt??

Danke für nen Tipp =)

1.549 Beiträge seit 2004
vor 18 Jahren

Warum willst du den alle Kombinationen anzeigen??

Du könntest ja ein Abbild deiner anzeige als int Array speichern dann läst du das mit Hilfe einer schleife durchgehen und fertig.

Wir Arbeiten eigendlich nicht wir nehmen nur das geld

B
189 Beiträge seit 2004
vor 18 Jahren

Original von KRAFT
Ich habe ein Schema mit 4 Feldern. Jedes dieser Felder kann einen von 3 Zustanden annehem (1,2,3). Die Anzahl der Möglichen Kombinatioen ist also 3 hoch 4 also 81 wenn ich das richtig sehe.

Nein, die Anzahl möglicher Kombinationen ist immer StellenZustände, in deinem Fall also 43 = 64.

Den Rest deiner Frage habe ich nicht verstanden... 😕

Q
992 Beiträge seit 2005
vor 18 Jahren

@bitstream: Ich denke, dass Kraft recht hatte: Ich habe bei einer Stelle drei Zustände also drei Möglichkeiten.
Dass macht also ZuständeStelle = 31 = 3.
Wäre es StelleZustände, dann wäre es 13 = 1.

Also ist 3^4=81 schon richtig. Ist ja auch logisch. Erst habe ich drei möglichkeiten, dann das dreifache von drei, dann das dreifache davon, usw.
Also 3,9,27,81.

Ich denke, dass das mit den Schleifen am schnellsten ist.


		int[,] fillpos()
		{
			int[,] returnvalue = new int[81,4];
			int[] looper = new int[4];

			int count = 0;

			for(looper[0] = 1; looper[0] < 4;looper[0]++)
			{
				for(looper[1] = 1; looper[1] < 4;looper[1]++)
				{
					for(looper[2] = 1; looper[2] < 4;looper[2]++)
					{
						for(looper[3] = 1; looper[3] < 4;looper[3]++)
						{
							returnvalue[count]=looper; //hier ist ein Problem! ich habe ein zweidimensionales Array und ein eindimensionales Array. Wie kann ich dem Array an der Stelle counter in der 1. ebene jetzt ein ganzes array zuweisen? Wie sieht das mit der Performance aus? Ist es gleich schnell in Arrays zu zählen oder ist es wesentlich schneller, wenn ich ne stinknormale variable nehme?
							count++;
						}
					}
				}
			}

		}	


B
189 Beiträge seit 2004
vor 18 Jahren

Original von Quallo
@bitstream: Ich denke, dass Kraft recht hatte: Ich habe bei einer Stelle drei Zustände also drei Möglichkeiten.
Dass macht also ZuständeStelle = 31 = 3.
Wäre es StelleZustände, dann wäre es 13 = 1.

Stimmt, ich habe mich geirrt. Ich bin da wohl mit den Begriffen Felder und Zustände durcheinander geraten...

Es verhält sich ja so wie bei den Zahlensystemen! Wenn man eine vierstellige Binärzahl hat, gibt es 24=16 Kombinationen. Übertragen auf KRAFTs Frage haben wir also eine vierstellige Ternärzahl, also 34=81 Kombinationen.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo zusammen,

81 ist richtig.

Wenn du die möglichen Kombinationen haben willst, geht das auch besser und vor allem allgemeiner als mit vier ineinandergeschachtelten Schleifen:


const int iDigitBase = 3;  // Anzahl der Zustände
const int iNumDigits = 4; // Anzahl der Felder

int [] iDigit = new int [iNumDigits];

int iNumCombinations = (int)Math.Pow (iDigitBase, iNumDigits);

for (int i = 0; i < iNumCombinations; ++i) {
   int i2 = i;
   Console.Write ((i2 + 1) + " = ");
   for (int i3 = 0; i3 < iNumDigits; ++i3) {
      iDigit [i3] = i2 % iDigitBase;
      i2 /= iDigitBase;
      Console.Write ((iDigit [i3] + 1) + ", ");
   }
   Console.WriteLine ();
}

herbivore

PS: Die Implementierung hat einige Schwächen, z.B. die Verwendung von Pow für int-Zahlen und die Ausgabe der Ziffern in der umgekehrten Reihenfolge inkl. überschüssigem Komma.

Q
992 Beiträge seit 2005
vor 18 Jahren

Habt ihr eine Lösung für den Kommentar in meinem Code?
herbivore vielleicht?
Der Name birgt doch sonst für Qualität g!

Grüße Christoph

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo Quallo,

danke für die Blumen. Leider erwischt du mich an einem schwachen Punkt, da ich kaum mehrdimensionale Arrays verwende. Anyway.

ich habe ein zweidimensionales Array und ein eindimensionales Array. Wie kann ich dem Array an der Stelle counter in der 1. ebene jetzt ein ganzes array zuweisen?

Ich denk, dass geht nur in einer Schleife mit Zuweisung der einzelnen Elemente. Oder du nimmst verzweige Arrays, also 'aai [1] [5]', dann kannst du Array.Copy bzw. Array.CopyTo benutzen. So oder so, muss performacetechnisch jedes Array-Element kopiert werden (was bei Array.Copy vermutlich etwas effizienter geht als von Hand).

Wie sieht das mit der Performance aus? Ist es gleich schnell in Arrays zu zählen oder ist es wesentlich schneller, wenn ich ne stinknormale variable nehme?

++i geht vermutlich ungefähr doppelt so schnell wie ++ai[j], aber da beides "keine" Zeit kostet, ist 2 mal Nullzeit immer noch Nullzeit 🙂 Will sagen, in den meisten Fällen wirst du keinen Unterschied spüren.

herbivore

Q
992 Beiträge seit 2005
vor 18 Jahren

Vielleicht schaffe ich es, da einen kleinen Performance-Test hinzubekommen. Habe aber momentan wenig Zeit.

Danke erstmal für den Tip!

Grüße Christoph

S
238 Beiträge seit 2004
vor 18 Jahren

Hmm, der Algorithmus funktioniert ja an sich schon mal ziemlich gut, habe den gerade mal getestet.

Kann man den irgendwie anpassen, damit er alle möglichen Kombinationen innerhalb eines char-Arrays ausgibt? Das versuche ich nämlich und komme nicht auf den richtigen Trichter. Hier soll ebenfalls die Länge der enstehenden Wörter anzugeben sein, während die Möglichkeiten der Zustände durch den Inhalt des Arrays gegeben werden.

Beispielhaft:

array ist {'a', 'b', 'c'}

Ausgabe soll sein:

a
b
c
aa
ab
ac
aaa
aab
aac
aba
abb
abc
...
usw.

Würde mich sehr freuen, wenn mir dazu jemand einen Tipp geben könnte!

Greets - SK

P.S: Es sieht zwar aus wie ein Bruteforce-Hacker-Tool welch Wort, soll aber keins sein. Dient mir eigentlich eher dazu, die möglichen Kombinationen in regulären Sprachen aufzudecken...

Sagte ich schon Danke? Nein? ...kommt noch...

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo Schattenkanzler,

naja, anpassen oder neu implementieren 🙂


private static void ErzeugeAlleWorte (String strBegin, char [] ach, int iLen)
{
   if (iLen <= 0) {
      Console.WriteLine (strBegin);
      return;
   }

   foreach (char ch in ach) {
      ErzeugeAlleWorte (strBegin + ch, ach, iLen - 1);
   }
}

herbivore

Nachtrag: So kann man die Methode komfortabel aufrufen:

public static void ErzeugeAlleWorte (String strInput)
{
   ErzeugeAlleWorte ("", strInput.ToCharArray (), strInput.Length);
}
S
238 Beiträge seit 2004
vor 18 Jahren

Wow, so kurz? Hab hier rumgeeiert bis zum getno...oh man! Danke dir, herb!

Greets - SK

Sagte ich schon Danke? Nein? ...kommt noch...

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo zusammen,

da ich gerade wieder über den Thread gestolpert bin, hier noch ein kleine Anmerkung.

Wenn man statt alle Kombinationen aus den Buchstaben nur alle Permutationen der Buchstaben haben möchte, dann reicht es vor den rekursiven Aufruf im foreach die Abfrage if (strBegin.IndexOf (ch) < 0) zu setzen(*). Bei der Eingabe "xy" bekommt man dann also statt allen Kombinationen (xx, xy, yx, yy) nur noch die Permutationen (xy, yx).

Das geht aber nur gut, solange jeder Buchstabe in der Eingabe nur genau einmal vorkommt. Hier eine Version von ErzeugeAllePermutationen die auch mit mehrfachen Vorkommen von Buchstaben klar kommt.

public static void ErzeugeAllePermutationen (String strInput)
{
   Dictionary <char, int> dictNumOccurrences = new Dictionary <char, int> ();
   foreach (char ch in strInput) {
      if (!dictNumOccurrences.ContainsKey (ch)) {
         dictNumOccurrences [ch] = 1;
      } else {
         ++dictNumOccurrences [ch];
      }
   }
   char [] ach = new char [dictNumOccurrences.Count];
   dictNumOccurrences.Keys.CopyTo (ach, 0);
   Array.Sort (ach);

   ErzeugeAllePermutationen ("", ach, dictNumOccurrences, strInput.Length);
}

private static void ErzeugeAllePermutationen (String strBegin,
                                              char [] ach,
                                              Dictionary <char, int> dictNumOccurrences,
                                              int iLen)
{
   if (iLen <= 0) {
      Console.WriteLine (strBegin);
      return;
   }

   foreach (char ch in ach) {
      if (dictNumOccurrences [ch] > 0) {
         --dictNumOccurrences [ch];
         ErzeugeAllePermutationen (strBegin + ch, ach, dictNumOccurrences, iLen - 1);
         ++dictNumOccurrences [ch];
      }
   }
}

ErzeugeAllePermutationen ("xxxyy") ergibt also:


xxxyy
xxyxy
xxyyx
xyxxy
xyxyx
xyyxx
yxxxy
yxxyx
yxyxx
yyxxx

Wie gesagt, wenn jedes Element nur einmal vorkommt, kann man auch das einfachere Snippet von oben plus die zusätzliche Abfrage verwenden.

herbivore

EDIT:

(*) Statt den rekursiven Aufruf in den Then-Teil von if (strBegin.IndexOf (ch) < 0) zu setzen, kann man auch folgende Zeile (1) vor den rekursiven Aufruf schreiben:

if (strBegin.IndexOf (ch) >= 0) { continue; }

Wenn man nicht die Permutation berechnen will, sondern die Kombinationen, die man - ohne Berücksichtigung der Reihenfolge - erhalten kann, wenn man aus dem Alphabet ach jeweils iLen-viele Buchstaben zieht (also analog der Lottozahlen, die am Ende auch aufsteigend geordnet sortiert gezeigt werden), dann kann man stattdessen folgende Zeile (2) vor den rekursiven Aufruf schreiben:

if (strBegin.Length > 0 && strBegin [strBegin.Length-1] <= ch) { continue; }

Die Buchstaben tauchen dann innerhalb der berechneten Kombinationen nur noch strikt aufsteigend geordnet auf. Damit erhält man also nur die normierten Kombinationen, die jeweils der Menge der enthaltenen Buchstaben entspricht.

Die Bedingung von Zeile 2 ist schließt die Bedingung von Zeile 1 mit ein. Es gibt also keinen Fall, in denen Bedingung 1 wahr ist, ohne dass Bedingung 2 nicht auch wahr ist. Wenn man Zeile 2 in den Code schreibt, ist folgerichtig Zeile 1 nicht mehr nötig.

Ich bin für die Nachvollziehbarkeit zunächst so nah wie möglich am Ausgangscode geblieben. Das ganze lässt sich jedoch noch etwas effizienter ermitteln.

Wenn man sich als Gedankenexperiment vorstellt, dass die Buchstaben in ach alphabetisch sortiert sind, sieht man, dass Zeile 2 dazu führt, dass immer nur Buchstaben angehängt werden, die von ihrer Indexposition strikt hinter allen Buchstaben stehen, die schon in strBegin enthalten sind.

Mit diesem Wissen lässt sich eine effizientere Implementierung finden, die an den rekursiven Aufruf zusätzlich die Indexposition des aktuellen Buchstabens übergibt. Dann kann man die Schleife nämlich so aufbauen, dass sie nur über die dahinterstehenden Buchstaben läuft.

Selbst wenn wir gedanklich jetzt einen Schritt zurückgehen und die Buchstaben als nicht mehr sortiert ansehen, sieht man, dass trotzdem alle gewünschten Kombinationen berechnet werden (wenn dann auch nicht mehr in alphabetisch aufsteigender Reihenfolge).

Im Ergebnis also bekommt man folgenden Code. Genau genommen wird dabei nicht der Index des aktuellen Buchstabens übergeben, sondern der jeweils nächste zu berücksichtigende Index. Gestartet wird mit Index 0, also ErzeugeAlleWorte3 ("", ach, 0, 5):


private static void ErzeugeAlleWorte (String strBegin, char [] ach, int iIndex, int iLen)
{
   if (iLen <= 0) {
      Console.WriteLine (strBegin);
      return;
   }
   for (int iCurrIndex = iIndex; iCurrIndex < ach.Length; ++iCurrIndex) {
      ErzeugeAlleWorte (strBegin + ach[iCurrIndex], ach, iCurrIndex + 1, iLen - 1);
   }
}

Diese Variante ist annähernd doppelt so schnell, wie die davor.

Sie ist allerdings etwas weniger robust und liefert die Kombinationen nur dann normiert und sortiert, wenn die Buchstaben in ach sortiert sind und keine doppelten enthalten.

Suchhilfe: 1000 Worte

107 Beiträge seit 2011
vor 12 Jahren

Hat jemand eine Idee, wie man die Permutationen iterativ generieren kann? Leider bekommt ja schon bei relativ kurzen Strings einen StackOverFlow. X(

q.e.d.

6.911 Beiträge seit 2009
vor 12 Jahren

Hallo ProgrammierTroll,

siehe Fisher-Yates-Shuffle und davon abgeleitete Varianten.
Für alle Permutationen zB Steinhaus–Johnson–Trotter Algorithmus.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

107 Beiträge seit 2011
vor 12 Jahren

Danke, letzterer war, was ich gesucht habe.

Ärgerlich, dass einem sowas nicht selbst einfällt. 8[

q.e.d.

6.911 Beiträge seit 2009
vor 12 Jahren

Hallo ProgrammierTroll,

Ärgerlich, dass einem sowas nicht selbst einfällt.

Stimmt. Aber selbst dann ist es schon publiziert worden und man zieht dennoch den Kürzeren.

Aber das ist das schöne an dieser Art von Algorithmen: genial einfach.*

* nur draufkommen muss man. Das ist der schwierigere Teil davon 😃

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

107 Beiträge seit 2011
vor 12 Jahren

Aber das ist das schöne an dieser Art von Algorithmen: genial einfach.*

* nur draufkommen muss man. Das ist der schwierigere Teil davon 😃){gray}

(
Habe diesen Alogrithmus im Studium nie kennengelernt, obwohl der eigentlich wesentlich inuitiver als der rekursive ist. Immerhin was dazu gelernt!

q.e.d.

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo ProgrammierTroll,

beim meinen Permutations-Snippet ist die maximale Rekursionstiefe gleich der die Länge des Eingabestrings. Da schon relativ kurze Eingabestrings sehr viele Permutationen besitzen, wird die Stackgröße sicher nicht das Problem sein. Bei vernünftigen Eingabelängen wirst du sicher keine StackOverflowException bekommen.

herbivore

107 Beiträge seit 2011
vor 12 Jahren

Ich habe Probleme bei Strings mit einer Länge von ca. 30 Zeichen bekommen.

Iterativ funktionuggelt das einwandfrei. 😁

q.e.d.

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo ProgrammierTroll,

bei einem String der Länge 30 mit 30 verschiedenen Zeichen gibt es 30! (=Fakultät von 30) Permutationen, also ca. 2,7 * 1032. Wenn wir hypothetisch und etwas überoptimistisch annehmen, dass der Rechner 1012 Permutationen pro Sekunde berechnen kann, dann wäre er erst nach 8,4 Billionen Jahren fertig.

Wenn in dem String einige Zeichen mehrfach vorkommen, reduziert sich die Anzahl etwas, aber vom Prinzip her ändert sich nichts.

30 ist also sicher keine vernünftige Eingabelänge.

Trotzdem habe mein Snippet eine Weile sogar mal mit einem String der Länge 62
("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") rechnen lassen. Wie erwartet: kein StackOverflow.

Rekursiv funktioniert also natürlich auch einwandfrei (und liefert zudem die Permutationen noch in der systematischen Reihenfolge).

Deshalb komme ich zu dem Schluss, dass du deinem Namen manchmal alle Ehre machst. 😃

herbivore