October 25th, 2015

nyaload

строка по номеру

Есть такой забавный рекурсивный алгоритм перечисления всех строк (использущий yield из питона):

letters = "abcdefghijklmnopqrstuvwxyz"
def all_strings():
    yield ''
    for s in all_strings():
        for c in letters:
            yield s + c


Чтобы перечислить все строки - перечисляем все строки и добавляем варианты суффиксов a,b,c,...,z. Благодаря yield '' у вложенных вызываемых генераторов всегда есть достаточно ответов для более высокоуровневых, и поэтому функция не зависает.


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

def string_by_index(i):                  
    if i == 0:                           
        return ''                        
                                         
    i -= 1                               
                                         
    s = string_by_index(i // len(letters))  
    return s + letters[i % len(letters)]