Feedback

C# - Erzeugen von Zeichenfolgen durch Permutation

Veröffentlicht von am 08.01.2011
(3 Bewertungen)
Diese Funktion erzeugt ein string-Array mit string-Elementen, die aus 'chars' unterschiedlichen Zeichen und 'places' Stellen bestehen. Das Array beinhaltet alle möglichen Verknüpfungsmöglichkeiten dieser Zeichen, mit gegebener Anzahl an Stellen.

Die Funktion GetPermutation() liefert ein string[] Array. (empfohlen)
Die Funktion GetPermutationPerRef() schreibt die Ergebnisse in die ebenfalls zu übergebende ArrayList.

/* Beispiel zur Generierung einer 3-stelligen Bitfolge und anschließende Ausgabe. */

string[] Variationen = GetPermutation(3, new char[] { '0', '1' });

foreach (string Variation in Variationen)
{
Console.WriteLine(Variation);
}
// Die folgende eine Zeile gehört an den Kopf der Seite
using System.Collections;

/// <summary>
/// Generiert ein Array, aus Elementen die jeweils aus 'chars' unterschiedlichen Zeichen bestehen, mit jeweils 'places' Stellen.
/// Das Array beinhaltet alle möglichen Verknüpfungsmöglichkeiten, die durch Permutation ermittelt werden.
/// </summary>
/// <param name="places">Anzahl der Stellen jedes Elements</param>
/// <param name="chars">Array von Zeichen die benutzt werden dürfen</param>
/// <returns>Ein string-Array mit allen unterschiedlichen Verknüpfungsmöglichkeiten</returns>
public static string[] GetPermutation(int places, char[] chars)
{
    // Eine neue, leere ArrayList generieren, an die alle Möglichkeiten angehängt werden
    ArrayList output = new ArrayList();
    GetPermutationPerRef(places, chars, ref output);

    // Das Ergebnis in einen string[] umwandeln und zurückgeben
    return output.ToArray(typeof(string)) as string[];
}

/// <summary>
/// Generiert ein Array, aus Elementen die jeweils aus 'chars' unterschiedlichen Zeichen bestehen, mit jeweils 'places' Stellen.
/// Das Array beinhaltet alle möglichen Verknüpfungsmöglichkeiten, die durch Permutation ermittelt werden.
/// Das Ergebnis wird in der als Referenz übergebenen ArrayList 'output' gespeichert.
/// </summary>
/// <param name="places">Anzahl der Stellen jedes Elements</param>
/// <param name="chars">Array von Zeichen die benutzt werden dürfen</param>
/// <param name="output">ArrayList in die alle Möglichkeiten hinzugefügt werden</param>
/// <param name="outputPart">Optionaler interner Parameter, zur Weitergabe der Informationen während des rekursiven Vorgangs</param>
private static void GetPermutationPerRef(int places, char[] chars, ref ArrayList output, string outputPart = "")
{
    if (places == 0)
    {
        // Wenn die Anzahl der Stellen durchgerechnet wurde,
        // wird der sich ergebende string (Element) an die Ausgabe angehängt.
        output.Add(outputPart);
    }
    else
    {
        // Für die Stelle rechts im Element, werden alle Zeichenmöglichkeiten durchlaufen
        foreach (char c in chars)
        {
            // Danach wird für jedes dieser Zeichen, basierend auf der Anzahl der Stellen, wieder ein neuer
            // foreach-Vorgang begonnen, der alle Zeichen der nächsten Stelle hinzufügt

            GetPermutationPerRef(places - 1,   // Die Stellen Anzahl wird verwindert, bis 0
                chars,                         // Benötigte Variablen werden
                ref output,                    // mitübergeben
                outputPart + c);               // An diesen letzen string werden alle anderen Stellen angehängt
        }
    }
}

2 Kommentare zum Snippet

Keks1911 schrieb am 10.01.2011:
In der jetzigen Form (und meiner Testkonfiguration) können maximal 10-stellige Permutationen errechnet werden, bevor der Speicher ausgeht. (also für places < 10)
marioka schrieb am 11.01.2011:
Hmm, ja leider. Bei 10 Stellen gibt es ja schon verdammt viele Möglichkeiten, wenn man viele Zeichen verwendet.
Man könnte bei der Funktion GetPermutationPerRef(), immer dann wenn die ArrayList.Count > 1.000.000 (angenommen) ist, das ganze in eine Datei schreiben und die ArrayList wieder löschen.
So kann man das ganze wenigstens auf die Festplatte auslagern und der RAM wird nicht belastet.

        private static void GetPermutationPerRef(int places, char[] chars, ref ArrayList output, string outputPart = "")
{
if (places == 0)
{
output.Add(outputPart);

if (output.Count > 1000000)
{
System.IO.StreamWriter sw = new System.IO.StreamWriter(@"permutation.txt", true);

foreach (string s in output)
{
sw.WriteLine(s);
}

sw.Close();
output.Clear();
}
}
...
...
 

Logge dich ein, um hier zu kommentieren!