Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets]
KRAFT
myCSharp.de - Member



Dabei seit:
Beiträge: 14

Themenstarter:

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

beantworten | zitieren | melden

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 =)
private Nachricht | Beiträge des Benutzers
S.H.-Teichhof
myCSharp.de - Member

Avatar #avatar-2460.jpg


Dabei seit:
Beiträge: 1552
Herkunft: Sindringen

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
bitstream
myCSharp.de - Member



Dabei seit:
Beiträge: 189
Herkunft: Hannover

beantworten | zitieren | melden

Zitat
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 Stellen^Zustände, in deinem Fall also 4^3 = 64.

Den Rest deiner Frage habe ich nicht verstanden... :-/
private Nachricht | Beiträge des Benutzers
Quallo
myCSharp.de - Member



Dabei seit:
Beiträge: 994
Herkunft: Nähe Bremen

beantworten | zitieren | melden

@bitstream: Ich denke, dass Kraft recht hatte: Ich habe bei einer Stelle drei Zustände also drei Möglichkeiten.
Dass macht also Zustände^Stelle = 3^1 = 3.
Wäre es Stelle^Zustände, dann wäre es 1^3 = 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++;
						}
					}
				}
			}

		}	

private Nachricht | Beiträge des Benutzers
bitstream
myCSharp.de - Member



Dabei seit:
Beiträge: 189
Herkunft: Hannover

beantworten | zitieren | melden

Zitat
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ände^Stelle = 3^1 = 3.
Wäre es Stelle^Zustände, dann wäre es 1^3 = 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 2^4=16 Kombinationen. Übertragen auf KRAFTs Frage haben wir also eine vierstellige Ternärzahl, also 3^4=81 Kombinationen.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Quallo
myCSharp.de - Member



Dabei seit:
Beiträge: 994
Herkunft: Nähe Bremen

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Quallo,

danke für die Blumen. Leider erwischt du mich an einem schwachen Punkt, da ich kaum mehrdimensionale Arrays verwende. Anyway.
Zitat
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).
Zitat
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
private Nachricht | Beiträge des Benutzers
Quallo
myCSharp.de - Member



Dabei seit:
Beiträge: 994
Herkunft: Nähe Bremen

beantworten | zitieren | melden

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

Danke erstmal für den Tip!

Grüße Christoph
private Nachricht | Beiträge des Benutzers
Schattenkanzler
myCSharp.de - Member



Dabei seit:
Beiträge: 239
Herkunft: Berlin

beantworten | zitieren | melden

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...
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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);
}
private Nachricht | Beiträge des Benutzers
Schattenkanzler
myCSharp.de - Member



Dabei seit:
Beiträge: 239
Herkunft: Berlin

beantworten | zitieren | melden

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

Greets - SK
Sagte ich schon Danke? Nein? ...kommt noch...
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
ProgrammierTroll
myCSharp.de - Member

Avatar #avatar-3285.jpg


Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

Hat jemand eine Idee, wie man die Permutationen iterativ generieren kann? Leider bekommt ja schon bei relativ kurzen Strings einen StackOverFlow. X(
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ProgrammierTroll am .
q.e.d.
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7510
Herkunft: Waidring

beantworten | zitieren | melden

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!"
private Nachricht | Beiträge des Benutzers
ProgrammierTroll
myCSharp.de - Member

Avatar #avatar-3285.jpg


Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

Danke, letzterer war, was ich gesucht habe.

Ärgerlich, dass einem sowas nicht selbst einfällt. 8[
q.e.d.
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7510
Herkunft: Waidring

beantworten | zitieren | melden

Hallo ProgrammierTroll,
Zitat
Ä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!"
private Nachricht | Beiträge des Benutzers
ProgrammierTroll
myCSharp.de - Member

Avatar #avatar-3285.jpg


Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

Zitat von gfoidl

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

* nur draufkommen muss man. Das ist der schwierigere Teil davon :-)


Habe diesen Alogrithmus im Studium nie kennengelernt, obwohl der eigentlich wesentlich inuitiver als der rekursive ist. Immerhin was dazu gelernt!
q.e.d.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
ProgrammierTroll
myCSharp.de - Member

Avatar #avatar-3285.jpg


Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

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

Iterativ funktionuggelt das einwandfrei.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ProgrammierTroll am .
Attachments
q.e.d.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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 * 10^32. Wenn wir hypothetisch und etwas überoptimistisch annehmen, dass der Rechner 10^12 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
private Nachricht | Beiträge des Benutzers