Какой хороший способ выяснить все возможные слова заданной длины - PullRequest
7 голосов
/ 23 ноября 2008

Я пытаюсь создать алгоритм на C #, который выдает следующие выходные строки:

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

Каков наилучший способ сделать это?

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

Ответы [ 12 ]

17 голосов
/ 23 ноября 2008

хорошо, если длина является константой 4, то с этим справится:

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

если длина является параметром, это рекурсивное решение будет обрабатывать его:

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;
    }
}
15 голосов
/ 23 ноября 2008

Всегда есть обязательная реализация LINQ. Скорее всего, бесполезная производительность, но с каких пор производительность мешает использовать новые интересные функции?

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' теперь будет IQueryable, который содержит от AAAA до ZZZZ.

Edit:

Хорошо, поэтому меня беспокоило, что с помощью LINQ можно создать последовательность настраиваемой длины с настраиваемым алфавитом. Так и здесь. Опять же, совершенно бессмысленно, но меня это беспокоило.

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

Вызов метода Sequence приводит к тому же списку AAAA-ZZZZ, что и раньше, но теперь вы можете изменить используемый словарь и продолжительность получаемых слов.

5 голосов
/ 25 ноября 2008

Просто комментарий к Гарри Шатлеру, но я хочу раскрасить код:

Вам действительно не нужно делать это IQuaryable, ни сортировать, так что вы можете удалить второй метод. Один шаг вперед состоит в том, чтобы использовать Aggregate для перекрестного продукта, в итоге это выглядит так:

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

Андерс должен получить Нобелевский приз за вещь Линка!

2 голосов
/ 24 ноября 2008

GNU Bash!

{a..z}{a..z}{a..z}{a..z}
1 голос
/ 05 января 2009

Упрощенный 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
1 голос
/ 25 ноября 2008

Это рекурсивная версия тех же функций в C #:

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace ConsoleApplication1Test
{
    class Program
    {
        static char[] my_func( char[] my_chars, int level)
        {
            if (level > 1)
                my_func(my_chars, level - 1);
            my_chars[(my_chars.Length - level)]++;
            if (my_chars[(my_chars.Length - level)] == ('Z' + 1))
            {
                my_chars[(my_chars.Length - level)] = 'A';
                return my_chars;
            }
            else
            {
                Console.Out.WriteLine(my_chars);
                return my_func(my_chars, level);
            }
        }
        static void Main(string[] args)
        {
            char[] text = { 'A', 'A', 'A', 'A' };
            my_func(text,text.Length);
            Console.ReadKey();
        }
    }
}

Печать из AAAA в ZZZZ

1 голос
/ 24 ноября 2008

Haskell!

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

рубин!

('A'*4..'Z'*4).to_a
1 голос
/ 24 ноября 2008

Python!

(Это всего лишь взлом, не принимайте меня всерьез: -)

# 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
1 голос
/ 23 ноября 2008

Вдохновленный ответом Гарри Шатлера, я решил перекодировать его ответ в T-SQL.

Скажем, «Письма» - это таблица с одним полем, MyChar, CHAR (1). В нем 26 строк, каждая буква алфавита. Итак, у нас есть (вы можете скопировать и вставить этот код на SQL Server и запустить как есть, чтобы увидеть его в действии):

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

Преимущества: это легко расширяется за счет использования заглавных / строчных букв или использования не латинских латинских символов (например, «С» или cedille, eszets и т. П.), И вы все равно получите заказанный набор, нужно только добавить сопоставление. Кроме того, SQL Server будет выполнять это немного быстрее, чем LINQ на одноядерном компьютере, а на многоядерных (или многопроцессорных) выполнение может выполняться параллельно, получая еще больший прирост.

К сожалению, он застрял для конкретного случая из 4 букв. Рекурсивное решение lassevk носит более общий характер, и попытка сделать общее решение в T-SQL обязательно подразумевает динамический SQL со всеми его опасностями.

0 голосов
/ 31 июля 2017

Очень простой, но потрясающий код, который генерирует все слова из 3 и 4 букв английского языка

#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
  }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...