Разберем следующую задачу
В алфавите языка племени «Тумба-Юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все слова, состоящие из n букв, которые можно построить из букв этого алфавита
Задача представляет собой обычную задачу на перебор, которую можно свести к задаче меньшего размера.
Будем последовательно подставлять буквы к слову.
На первой позиции слова может стоять одна из 4х букв алфавита (K. L, M, N)
Cначала первой поставим букву 'K'. Тогда для того, чтобы получить все варианты с первой буквой 'K', нужно перебрать все возможные комбинации букв на оставшихся n-1 позициях.
и .т.д. (см. рисунок)
Таким образом, мы вышли на рекурсивное решение: цикле перебрать все возможные первые буквы (ставя по очереди каждую букву алфавита на первое место) и для каждого случая построить все возможные "хвосты" длиной n-1
Рекурсивный перебор символов
Остановить рекурсию и вывести готовое слово нужно тогда, когда оставшаяся часть пустая (n = 0), т.е. все буквы уже выраны.
Рекурсивная процедура будет выглядеть следующим образом:
def TumbaWords(word, alphabet, n):
if n < 1:
print(word)
return
for c in alphabet:
TumbaWords(word+c, alphabet, n - 1)