Генерация всех возможных хорошо упорядоченных строковых перестановок - PullRequest
Новая
       25

Генерация всех возможных хорошо упорядоченных строковых перестановок

1 голос
/ 11 января 2020

Мне задали этот вопрос на собеседовании. Я думал об этом, но не смог найти решение.

Вот проблема: вы знаете, что пароль состоит только из букв и хорошо упорядочен, что означает, что символы в пароле расположены в алфавитном порядке.

Например, пароль 4 di git может быть «abxz» или «aBkZ», но не «aAxz» или «baxz».

Напишите функцию, которая генерирует все действительные пароли с учетом его длины. Не забывайте, что он должен генерировать все возможные комбинации с верхним и нижним символами. Например: «aBcd», «Abcd», «abcd», «AbCd» - это разные действительные пароли.

Я думаю, что алгоритм должен быть рекурсивным. Однако пока ничего не получалось. Я попробовал следующее. 

def func(number, start_letter ='A',  match = ''):
    if number == 0:
        print(match)
    else:
        for i in range(ord(start_letter), 70):
            func(number-1, chr(ord(start_letter)+1),match + chr(i))

Пожалуйста, спасите меня от моих страданий.

Редактировать: я не буду утверждать решение с помощью itertool. Я думаю, что другое решение менее зависит от языка и может быть легко написано на других языках.

Ответы [ 2 ]

2 голосов
/ 11 января 2020

Используя itertools, находит те же 239200 строк, что и у @ ggorlen. 

from string import ascii_uppercase
from itertools import combinations, product

def all_alphabetical_pw(length):
    for c in combinations(ascii_uppercase, length):
        for p in product(*zip(c, map(str.lower, c))):
            yield ''.join(p)

И вариант, не уверен, какой мне больше нравится: 

def all_alphabetical_pw(length):
    for c in combinations(zip(ascii_uppercase, ascii_lowercase), length):
        for p in product(*c):
            yield ''.join(p)

Обе работают по производит комбинаций , таких как (('D', 'd'), ('I', 'i'), ('N', 'n'), ('O', 'o')), а затем их продуктов , давая кортежи, подобные ('D', 'i', 'n', 'O'), которые просто необходимо объединить. Эти два решения отличаются только тем, что я превращаю буквы типа 'D' в пары типа ('D', 'd').

Первая версия делает это после , получая комбинации типа ('D', 'I', 'N', 'O'), превращая каждую такую ​​комбинацию в комбинацию (верхняя, нижняя) пар.

Вторая версия делает это до , создавая комбинации, вместо этого создавая пары для всего алфавита один раз. Это более эффективно и выглядит чище. Хорошо, я предпочитаю это сейчас.

Тесты: 

@ggorlen's  0.199 seconds
my first    0.094 seconds
my second   0.072 seconds

Измеряется так: 

timeit(lambda: list(all_alphabetical_pw(4)), number=100) / 100

О, еще один. Занимает 0,056 секунды, поэтому он самый быстрый, но мне он нравится меньше: 

def all_alphabetical_pw(length):
    for c in combinations(zip(ascii_uppercase, ascii_lowercase), length):
        yield from map(''.join, product(*c))
1 голос
/ 11 января 2020

Рекурсия прекрасно работает здесь. Выберите начальную букву и выполняйте итерации только из оставшихся букв, повторяя их в верхнем и нижнем регистре и увеличивая начальную букву по пути. Базовый случай - это когда длина строки, которую мы строим, равна целевой длине. Экспоненциальная сложность времени. 

def all_alphabetical_pw(length, start=65, pw=""):
    if len(pw) == length:
        yield pw
    else:
        for i in range(start, 91):
            yield from all_alphabetical_pw(length, i + 1, pw + chr(i))
            yield from all_alphabetical_pw(length, i + 1, pw + chr(i).lower())

if __name__ == "__main__":
    pws = list(all_alphabetical_pw(4))
    print(len(pws), "\n")

    for pw in pws[:10]: 
        print(pw)

    print("...")

    for pw in pws[-10:]: 
        print(pw)

Вывод: 

239200

ABCD
ABCd
ABCE
ABCe
ABCF
ABCf
ABCG
ABCg
ABCH
ABCh
...
WxyZ
Wxyz
wXYZ
wXYz
wXyZ
wXyz
wxYZ
wxYz
wxyZ
wxyz
...