Вывод ответа #1865291691

 # coding: utf8

word = "211221-21221"
word1, word2 = word.split('-')
# чтобы не усложнять код, вместо кириллицы
# использованы латинские аналоги букв
mnemonics = {'1': 'A', '2': 'B', '11': 'J', '12': 'K', '21': 'U', '22': 'F'}

def words(word, slice_size, slices_array=[]):
    all_words = []
    slice, word = mnemonics[word[:slice_size]], word[slice_size:]
    if word:
        for array in words(word, 1, slices_array + [slice]):
            all_words.append(array)
        if len(word) > 1:
            for array in words(word, 2, slices_array + [slice]) :
                all_words.append(array)
    else:
        all_words.append(slices_array + [slice])
    return map(''.join, all_words)

print words(word1, 1) + words(word1, 2)
print words(word2, 1) + words(word2, 2)

-------------
добавлено в 12.39: Хотелось бы сказать спасибо эссе Гвидо о графах. Напрямую не пригодилось (хотя я и пытался его код использовать), но какие-то идеи я уловил.
-------------
добавлено в 12.51: И я сейчас подумал, all_words и slices_array надо на кортежи заменить, тогда еще и эффективно будет в плане памяти. Изначально использование списков было необходимо.