?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
строка по номеру
nyaload
_winnie
Есть такой забавный рекурсивный алгоритм перечисления всех строк (использущий 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)] 
Tags:


  • 1
Это прекрасно.

//

Иначе получится бесконечная рекурсия.

Вариант без рекурсии:


letters = "abcdefghijklmnopqrstuvwxyz"
def string_by_index(i):
    s = ''
    n = len(letters)
    while i:
        i, j = divmod(i-1, n)
        s += letters[j]
    return s[::-1]

> //
> Иначе получится бесконечная рекурсия.
Я чувствую, сишные привычки записи деления ещё не раз меня подведут при переходе с Python2 на Python3. Поправил, спасибо.

> Вариант без рекурсии:
Компактненько!

Edited at 2015-10-25 03:40 pm (UTC)

ну да, так и нужно писать. Меня здесь только озадачивает мемори футпринт генераторов, ведь можно обойтись одной-двумя строками (в смысле, объектами).

  • 1