Как сделать такой перебор через itertools на Python?

Question

[Антон]

Приветствую, подскажите пожалуйста, есть такой код перебора строки из символов:

for i in itertools.product('123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz', repeat=10):
            pass = ''.join(i)

Он перебирает строку с 1111111111
А как мне сделать чтобы я мог указать в переменной свою строку например 1Mn2fqkfWo и чтобы шел перебор от этой строки с указанным набором символов и длиной?

Answer 1

[Сергей П]

Можно определить функцию инкремента для вашего "числа" с заданным набором "цифр" (алфавитом).
Например так:

def inc(s, ab='123abc'):
    if not s:
        return ''
    x = (ab.index(s[-1]) + 1) % len(ab)
    return (s[:-1] if x else inc(s[:-1])) + ab[x]

Теперь вы для любой строки с заданным алфавитом можете вычислить следующую в алфавитном порядке.
Для оптимизации скорости генерации лучше представить алфавит в виде словаря, а не строки:

alphabet_dict = dict(enumerate(alphabet_string))
alphabet_dict.update(zip(alphabet_string, range(len(alphabet_string))))

Тогда в функции надо ab.index(...) заменить на ab[...].
Теперь поиск индекса символа будет происходить за O(1).

Comments

[Антон]

Спасибо за пример! Но немного не разобрался как поставить его на перебор, вот пример кода:

def inc(s, ab='abcdef'):
    if not s:
        return ''
    x = (ab.index(s[-1]) + 1) % len(ab)
    return (s[:-1] if x else inc(s[:-1])) + ab[x]

while True:
    string = inc("abcd")
    print(string)

Результат выполнения:
abce
abce
abce
.........
А как сделать чтобы перебирал?

[Сергей П]

не, ну тут у вас совсем беда с основами алгоритмизации.

x = 'abcd'
while True:
    print(x)
    x = inc(x)

Но я бы предпочел вариант с генератором:

def gen(start, alphabet, end=None):
    if start != end:
        end = end or start
        yield start
        value = inc(start, alphabet)
        while value != end:
            yield value
            value = inc(start, alphabet)

for x in gen('aabb', 'abcd'):
    print(x)

# напечатает все коды от 'aabb', 'aabc', 'aabd', ... 'dddd', 'aaaa', 'aaab' и до 'aaba'

Да, я привёл вариант с рекурсивной функцией инкремента. В питоне нет оптимзации хвостовой рекурсии, так что возможно эффективнее для быстрого подбора будет сделать итеративный алгоритм, хотя он и буде чуть сложнее выглядеть.

[Антон]

Сергей Паньков, Спасибо за разъяснение, попробую применить на практике!

Answer 2

[Vindicar]

Никак. Я бы решил по-другому.
Рассматривай твою строку как число в N-рной системе счисления.
Например, если среди символов строки могут быть только цифры 0-9 - это будут десятичные числа.
Если будут a-z - то получим систему счисления с основанием 26.

Тогда каждой строке можно будет соспоставить число - номер этой строки в списке всех возможных строк. В твоём случае "1111111111" соотвествует номер 0, "1111111112" - номер 1, и так далее.

Соответственно, перебор строк будет сводиться к перебору всех чисел от 0 до числа возможных строк, с последующим переводом в выбранную "систему счисления". А остановка и возобновление перебора - сведётся к запоминанию текущего числа и выбору другой начальной позиции в следующий раз.

Хотя можно и попытаться пропустить N первых строк в выхлопе product(), но это будет медленно, если нужно начать где-то в конце.

Answer 3

[v1olet]

from itertools import product as pd
k = 0

for i in pd('заходитулиткавбар', repeat = 6):
    s = ''.join(i)
    k += 1
    if s == 'улитка':
        print(k)
    if k >= 10633655:
        print(s)

10633655 - первая встреча со словом улитка.
к - это костыль, так как нет в product такого параметра как перебор с конкретного слова.
Но чтобы решить ваш вопрос, такой костыль должен помочь

хочу посоветовать вам видео Кабанова по разбору ЕГЭ.
оно длинное, но вам станет понятно все о комбинаторике.
https://www.youtube.com/watch?v=xElROiCJvg8

Comments

[Антон]

Интересный костыль, но мой вопрос к сожалению не решает, выставить число на пару символов больше и сиди жди 10 минут пока скрипт проработает до этого момента, не практично...(