Co to dobry sposób na zastanawianie się wszystkie możliwe słowa danej długości

Question

staram się stworzyć algorytm w C#, który produkuje następujące ciągi wyjściowe:

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

Jaki jest najlepszy sposób, aby osiągnąć ten cel?

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

Answer 1

również, jeżeli długość jest stała 4, wówczas będzie to obsługiwać:

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; 
       } 
      } 
     } 
    } 
} 

jeśli długość jest parametrem, to rekursywne rozwiązanie go obsługiwać:

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

Zawsze obowiązuje obowiązkowa implementacja LINQ. Najprawdopodobniej śmieci, ale od kiedy wydajność przeszkadza w korzystaniu z nowych, fajnych funkcji?

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 }); 

"Sekwencja" będzie teraz wersją IQueryable zawierającą AAAA do ZZZZ.

Edit:

Ok, więc to był podsłuch mi, że powinno być możliwe, aby sekwencję długości konfigurowalnego z konfigurowalnym alfabetu przy użyciu LINQ. Więc oto jest. Znowu kompletnie bez sensu, ale mnie to dręczyło.

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; 
} 

Wywołanie metody Sequence daje ten sam AAAA do listy ZZZZ jak wcześniej, ale teraz można zmienić słownik używany i jak długo będzie produkowane słowa.

Answer 3

Zainspirowany odpowiedzią Garry'ego Shutlera, postanowiłem przekodować jego odpowiedź w T-SQL.

Powiedz "Listy" to tabela zawierająca tylko jedno pole, MyChar, CHAR (1). Ma 26 wierszy, każdy jest literą alfabetu. Tak musielibyśmy (można skopiować i wkleić ten kod na SQL Server i uruchomić jak jest zobaczyć go w akcji):

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 

Zaletami są: Jest łatwo rozszerzalny do korzystania Capital/małymi literami lub przy użyciu nie-angielskie znaki alfabetu łacińskiego (myśl "Ñ" lub cedille, eszets i tym podobne), a nadal będziesz otrzymywać uporządkowany zestaw, wystarczy dodać zestawienie. Plus SQL Server wykona to nieco szybciej niż LINQ na maszynie z pojedynczym rdzeniem, na wielordzeniowych (lub wieloprocesorowych) wykonanie może być równoległe, uzyskując jeszcze więcej boostu.

Niestety, utknęła ona w przypadku 4 liter. Rozwiązanie rekurencyjne lassevk jest bardziej ogólne, próba stworzenia ogólnego rozwiązania w T-SQL musiałaby oznaczać dynamiczny SQL ze wszystkimi niebezpieczeństwami.

Answer 4

javascript!

var chars = 4, abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ", top = 1, fact = []; 
for (i = 0; i < chars; i++) { fact.unshift(top); top *= abc.length; } 
for (i = 0; i < top; i++) 
{ 
    for (j = 0; j < chars; j++) 
     document.write(abc[Math.floor(i/fact[j]) % abc.length]); 
    document.write("<br \>\n"); 
} 

Answer 5

Python!

(to tylko hack, nie”weź mnie zbyt poważnie :-)

# Convert a number to the base 26 using [A-Z] as the cyphers 
def itoa26(n): 
    array = [] 
    while n: 
     lowestDigit = n % 26 
     array.append(chr(lowestDigit + ord('A'))) 
     n /= 26 
    array.reverse() 
    return ''.join(array) 

def generateSequences(nChars): 
    for n in xrange(26**nChars): 
     string = itoa26(n) 
     yield 'A'*(nChars - len(string)) + string 

for string in generateSequences(3): 
    print string 

Answer 6

Haskell!

replicateM 4 ['A'..'Z'] 

Rubin!

('A'*4..'Z'*4).to_a 

Answer 7

GNU Bash!

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

Answer 8

Tylko Coment do Garry Shutler, ale chcę kodu kolorystyka:

Naprawdę nie trzeba zrobić to IQuaryable, ani porządek, więc można wyjąć drugą metodę. Jeden krok forwad jest stosowanie łącznie dla produktu poprzecznym, to kończy się tak:

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 powinien dostać nagrodę Nobla za rzeczy Linq!

Answer 9

użyć czegoś co automatycznie gogli dla każdej kombinacji pojedynczą literę, a następnie sprawdzić, czy są bardziej „.sz” lub „.af” Hits następnie „.com” uderza w pięciu pierwszych wyników ...;)

Poważnie, co szukasz może być Próbuje (struktura danych), choć trzeba jeszcze zapełnić rzeczą, która prawdopodobnie jest o wiele trudniejsze ...

Answer 10

to jest rekurencyjna wersja tych samych funkcji w języku C#:

Wydruk od AAAA do ZZZZ

Answer 11

Prostszy python!

def getWords(length=3): 
    if length == 0: raise StopIteration 
    for letter in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ': 
     if length == 1: yield letter 
     else: 
      for partialWord in getWords(length-1): 
       yield letter+partialWord 

Answer 12

Bardzo proste, ale niesamowite kod, który generuje wszystkie słowa 3 i 4 litery języka angielskiego

#include <iostream> 
using namespace std; 
char alpha[26]={'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'} 
int main() { 
int num; 
cin >> num; 
if (num == 3) { //all 3 letter words 
    for (int i = 0; i <= 25; i++) { 
     for (int o = 0; o <= 25; o++) { 
      for (int p = 0; p <= 25; p++) { 
       cout << alpha[i] << alpha[o] << alpha[p] << " "; 
      } 
     } 
    } 
} 
else if (num == 4) { //all 4 letter words 
    for (int i = 0; i <= 25; i++) { 
     for (int o = 0; o <= 25; o++) { 
      for (int p = 0; p <= 25; p++) { 
       for (int q = 0; q <= 25; q++) { 
        cout << alpha[i] << alpha[o] << alpha[p] << alpha[q] << " "; 
       } 
      } 
     } 
    } 
} 
else { 
    cout << "Not more than 4"; //it will take more than 2 hours for generating all 5 letter words 
    } 
}