Создание списков слов с различной длиной слова? - PullRequest
Новая
       12

Создание списков слов с различной длиной слова?

1 голос
/ 29 апреля 2011

Я хочу создавать списки слов с разной длиной слова. мой источник для ...

длина = 1: 

for(int a=97;a<=122;a++)
   String foo=String.valueOf((char)a);

длина = 2: 

for(int a=97;a<=122;a++)
    for(int b=97;b<=122;b++) 
       String foo=String.valueOf((char)a+""+(char)b);

Есть идеи, как улучшить этот код, чтобы он не зависел от фактической длины строки?

Ответы [ 4 ]

3 голосов
/ 29 апреля 2011

Если бы ваша строка была числом, вы могли бы получить все возможные значения, просто добавив одно, пока число не переполнилось.просто считайте каждый символ цифрой;добавьте один самый правый символ;если он переносится, увеличивайте следующий символ и т. д. 

// for strings of size N
char *str = malloc(N+1);
// init
str[N] = 0;
for (i=0, i<N, i++) str[i]='a';

int done = 0;
while (!done)
{
    for(i=N-1; i>=0; i--)
    {
        str[i] += 1;
        if (str[i] == 'z'+1) 
        {
            if (N==0) done = 1;
            str[i] = 'a';
        }
        else break;
    }
    // do something with str
}
2 голосов
/ 29 апреля 2011

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

В любом случае рекурсия - лучший способ справиться с этим.1003 * 

List<String> generate(int len) {
    if(len == 1) {
        List<String> strings = new LinkedList<String>();
        // notice I'm putting a char here, not an int
        for(char a=97;a<=122;a++) strings.add(String.valueOf(a));
        return strings;
    }
    List<String> shortStrings = generate(len - 1);
    List<String> strings = new LinkedList<String>();
    for(String shortString : shortStrings)
        for(char a=97;a<=122;a++) strings.add(shortString + A);
    return strings;
}
0 голосов
/ 29 апреля 2011

Если я не совсем ошибаюсь, вы пытаетесь сгенерировать все возможные строки длины <=N.

Самый простой способ сделать это - сопоставить это скакие числа генерируются, то есть путем добавления 1 к числу, чтобы получить следующий номер.Так что в основном начните с "a", затем добавьте 1 к нему, чтобы получить "b" и так далее до "z".Теперь добавление 1 к этому вызовет перенос, поэтому сгенерируйте "aa", а затем "ba" и так до тех пор, пока "za" не станет "ab".

Вы можете значительно упростить это, если сможете отобразитьнатуральное число в строку.Чтобы получить строку, просто сделайте это: 

string getString(int val) {
    string str = "";
    while (val>=0) {
        int rem = val%26; // as there are 26 characters in english
        str = str + charToString('a'+rem);
        val /= 26;
    }
    return str;
}

Теперь просто вызовите эту функцию, чтобы получить строки: 

void listStrings(int N) {
    int max = 26^N-1;
    string str;
    for(int i=1; i<=max; ++i) {
        str = getString(i);
        doSomething(str); // maybe print it or store in file
    }
}

Надеюсь, это поможет вам.

0 голосов
/ 29 апреля 2011

Как подсказывает Tejs, вы захотите использовать рекурсию. Вы не можете писать циклы, чтобы иметь динамическую глубину, но вы можете вернуться к любому уровню, который вы хотите (по крайней мере, пока вы не исчерпаете пространство стека): 

//Pseudocode!
void generate(dictionary, string, depth)
{
    if(depth == 0)
    {
        dictionary.add(string);
    }
    else
    {
        for(char c = 'a'; c <= 'z'; ++c)
        {
            generate(dictionary, string + c, depth - 1);
        }
    }
}

Просто начните, если выключен, как: 

dictionary = new Dictionary;
generate(dictionary, '', depth);

и ты ушел. Если вы хотите включить все строки от до нужной длины, это простая настройка - просто всегда добавляйте строку в словарь, но повторяйте только, если текущая глубина больше нуля.

Надеюсь, это поможет!

...