Генерация всех подстрок (в лексикографическом порядке c) данной строки в алфавитном порядке

Question

Я недавно видел эту проблему и действительно застрял в ее реализации.

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

Меньший пример : Для строки xcv

мне необходимо сгенерировать вывод:

c cv cvx v vx x

Пример большего размера : Для строки hgrte

Мне необходимо сгенерировать следующие подстроки:

e
eg
egh
eghr
eghrt
eght
egr
egrt
egt
eh
ehr
ehrt
eht
er
ert
et
g
gh
ghr
ghrt
ght
gr
grt
gt
h
hr
hrt
ht
r
rt
t

Это моя реализация, которая не выдает желаемый вывод.

s = sorted(list(input()))
s = ''.join(s)
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        temp = s[i:j]
        print(''.join(temp))

Это вывод моего кода:

e
eg
egh
eghr
eghrt
g
gh
ghr
ghrt
h
hr
hrt
r
rt
t
[]

Я знаю, что должен использовать возврат и рекурсию после печати eghrt, но я действительно застрял в ее реализации. Заранее спасибо:)

Answer 1

Вы можете перебирать различные длины и использовать itertools.combinations для получения комбинаций букв:

from itertools import combinations
s = sorted(input())
print(*sorted(''.join(c) for i in range(len(s)) for c in combinations(s, i + 1)), sep='\n')

Answer 2

Вы можете сделать это без рекурсии, если рекурсия не является явным требованием:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

for w in (''.join(sorted(x)) for x in powerset(s) ):
    print(w)

Функция powerset взята из Как получить все подмножества набора? (Powerset)

Answer 3

Вы забыли рассмотреть непоследовательные подстроки. Простой способ сделать это с помощью itertools.

import itertools

word = sorted(list(input()))
print(sorted(set([''.join(j) for i in range(len(word)) for j in itertools.combinations(word, i)])))

Это сделает эту работу. Если вы предпочитаете не использовать стандартную библиотеку, вы можете использовать битовую маскировку для получения всех возможных подстрок.