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
