Генерация общего количества комбинаций n-буквенного алфавита в C
Я должен написать логику для создания комбинации n-буквенных слов.
Например, если указано число 2, мне нужно сгенерировать все двухбуквенные слова от az, то есть:
aa-ba-ca.....za
ab-bb-cb.....zb
.
.
.
.
az-bz........zz
Я понял, что вложенных циклов для этой задачи недостаточно, так как количество вложенных циклов меняется в зависимости от количества букв в слове. Это обращает меня к рекурсии, но я не могу придумать логику.
Почему это помечено language-agnostic еще в названии, которое вы указываете in C?
@GuyCoder Название имеет C, но вопрос был помечен как Java.
Ответы 3
Рекурсия здесь ключевая. Вот пример, написанный на Java:
public static void printCombos(int totalWords, String s) {
if (totalWords-- <= 0) {
System.out.print(s + " ");
return;
}
for(char i = 'a'; i <= 'z'; i++)
printCombos(totalWords, s + Character.toString(i));
System.out.println();
}
Вызовите его:
printCombos(2, "");
Есть 26^2 комбинаций для двух букв, 26^3 комбинаций для трех букв и так далее - 26^n комбинаций для n букв.
Таким образом, вы можете просто сделать один цикл для значений 0..26 ^ n-1 и построить соответствующие комбинации для каждого значения счетчика цикла.
Python-подобный псевдокод:
result = [""] * n
for i in range(26**n):
t = i
for k in range(n):
digit = t % 26
result[k] = letter[digit] #"a" for 0, "b" for 1 etc
t = t // 26
print(result)
Смысл этого урока в том, чтобы научить вас рекурсии, которая гораздо более ценна, чем педантичная щепетильность... но просто чтобы быть противным, вы можете полностью сделать это с вложенными циклами, если хотите. Вы можете сделать это с помощью цикла не вложенный...
void up_to_n_letters(int n)
{
char word[n];
int i = 0;
for (char letter = 'a'; i < n; letter++) {
word[i] = letter;
printf("%s,\n", word);
if (letter == 'z') {
letter = 'a' - 1;
i++;
}
}
}
Подумайте, как бы вы реализовали это для n=1. Затем подумайте, как бы вы реализовали это для n=2, учитывая результаты для n=1. Затем распространите это на n в целом.