Пушыстый (_winnie) wrote,
Пушыстый
_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: soft-dev
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments