Wie kann man alle möglichen Wörter mit einer bestimmten Länge herausfinden?

Question

Ich versuche, einen Algorithmus in C# zu erstellen, der die folgenden Ausgabestrings erzeugt:

AAAA
AAAB
AAAC
...and so on...
ZZZX
ZZZY
ZZZZ

Wie lässt sich dies am besten bewerkstelligen?

public static IEnumerable<string> GetWords()
{
    //Perform algorithm
    yield return word;
}

Answer 1

Nun, wenn die Länge eine Konstante 4 ist, dann würde dies zu behandeln:

public static IEnumerable<String> GetWords()
{
    for (Char c1 = 'A'; c1 <= 'Z'; c1++)
    {
        for (Char c2 = 'A'; c2 <= 'Z'; c2++)
        {
            for (Char c3 = 'A'; c3 <= 'Z'; c3++)
            {
                for (Char c4 = 'A'; c4 <= 'Z'; c4++)
                {
                    yield return "" + c1 + c2 + c3 + c4;
                }
            }
        }
    }
}

wenn die Länge ein Parameter ist, würde diese rekursive Lösung sie behandeln:

public static IEnumerable<String> GetWords(Int32 length)
{
    if (length <= 0)
        yield break;

    for (Char c = 'A'; c <= 'Z'; c++)
    {
        if (length > 1)
        {
            foreach (String restWord in GetWords(length - 1))
                yield return c + restWord;
        }
        else
            yield return "" + c;
    }
}

Answer 2

Es gibt immer die obligatorische LINQ-Implementierung. Wahrscheinlich ist die Leistung miserabel, aber seit wann steht die Leistung der Nutzung cooler neuer Funktionen im Weg?

var letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();

var sequence = from one in letters
               from two in letters
               from three in letters
               from four in letters
               orderby one, two, three, four
               select new string(new[] { one, two, three, four });

sequence' wird nun ein IQueryable sein, das AAAA bis ZZZZ enthält.

Editar:

Ok, so war es bugging mich, dass es möglich sein sollte, eine Folge von konfigurierbaren Länge mit einem konfigurierbaren Alphabet mit LINQ zu machen. Also hier ist es. Wieder, völlig sinnlos, aber es war mir ein Dorn im Auge.

public void Nonsense()
{
    var letters = new[]{"A","B","C","D","E","F",
                        "G","H","I","J","K","L",
                        "M","N","O","P","Q","R","S",
                        "T","U","V","W","X","Y","Z"};

    foreach (var val in Sequence(letters, 4))
        Console.WriteLine(val);
}

private IQueryable<string> Sequence(string[] alphabet, int size)
{
    // create the first level
    var sequence = alphabet.AsQueryable();

    // add each subsequent level
    for (var i = 1; i < size; i++)
        sequence = AddLevel(sequence, alphabet);

    return from value in sequence
           orderby value
           select value;
}

private IQueryable<string> AddLevel(IQueryable<string> current, string[] characters)
{
    return from one in current
           from character in characters
           select one + character;
}

Der Aufruf der Methode "Sequence" erzeugt die gleiche Liste von AAAA bis ZZZZ wie zuvor, aber jetzt können Sie das verwendete Wörterbuch und die Länge der erzeugten Wörter ändern.

Answer 3

Nur eine Bemerkung zu Garry Shutler, aber ich möchte Codefärbung:

Sie müssen es wirklich nicht IQuaryable, weder die Art, so können Sie die zweite Methode zu entfernen. Ein Schritt weiter ist es, Aggregate für das Kreuzprodukt zu verwenden, es endet wie folgt:

IEnumerable<string> letters = new[]{
                "A","B","C","D","E","F",                       
                "G","H","I","J","K","L",
                "M","N","O","P","Q","R","S",           
                "T","U","V","W","X","Y","Z"};

var result = Enumerable.Range(0, 4)
                .Aggregate(letters, (curr, i) => curr.SelectMany(s => letters, (s, c) => s + c));

foreach (var val in result)
     Console.WriteLine(val);

Anders sollte einen Nobelpreis für die Linq-Sache bekommen!

Answer 4

GNU Bash!

{a..z}{a..z}{a..z}{a..z}

Answer 5

Angeregt durch die Antwort von Garry Shutler habe ich beschlossen, seine Antwort in T-SQL umzukodieren.

Sagen wir, "Letters" ist eine Tabelle mit nur einem Feld, MyChar, einem CHAR(1). Sie hat 26 Zeilen, jede ein Buchstabe des Alphabets. Wir hätten also (Sie können diesen Code in SQL Server kopieren und so ausführen, wie er ist, um ihn in Aktion zu sehen):

DECLARE @Letters TABLE (
    MyChar CHAR(1) PRIMARY KEY
)
DECLARE @N INT
SET @N=0
WHILE @N<26 BEGIN
    INSERT @Letters (MyChar) VALUES ( CHAR( @N + 65) )
    SET @N = @N + 1
END
-- SELECT * FROM @Letters ORDER BY 1

SELECT A.MyChar, B.MyChar, C.MyChar, D.MyChar
FROM @Letters A, Letters B, Letters C, Letters D
ORDER BY 1,2,3,4

Die Vorteile sind: Es ist leicht erweiterbar, um Groß-/Kleinschreibung oder nicht-englische lateinische Zeichen zu verwenden (z.B. "Ñ" oder Cedille, Eszets und dergleichen), und Sie erhalten immer noch eine geordnete Menge, müssen nur eine Sortierung hinzufügen. Außerdem wird SQL Server dies etwas schneller als LINQ auf einem Einzelkernrechner ausführen, auf Multicore- (oder Multiprozessor-) Rechnern kann die Ausführung parallel erfolgen, was einen noch größeren Schub bedeutet.

Leider ist es für den speziellen Fall mit 4 Buchstaben festgefahren. lassevks rekursive Lösung ist allgemeiner, der Versuch einer allgemeinen Lösung in T-SQL würde zwangsläufig dynamisches SQL mit all seinen Gefahren bedeuten.