поиск всех возможных подпоследовательностей в заданной строке

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

from itertools import combinations_with_replacement
s = 'MISSISSIPPI'
lst = []
for i,j in combinations_with_replacement(range(len(s)), 2):
        print(s[i:(j+1)])

python combinations subsequence
person challenger    schedule 20.12.2019    source источник
comment
Не совсем понятно, что вы просите. Не могли бы вы привести конкретный пример более короткого слова?   -  person Dragon    schedule 20.12.2019
comment
Зачем использовать combinations_with_replacement вместо combinations, если вам нужны подпоследовательности?   -  person kaya3    schedule 20.12.2019

Ответы (2)


arrow_upward
3
arrow_downward

Используйте combinations для получения подпоследовательностей. Вот для чего нужен combinations.

from itertools import combinations

def all_subsequences(s):
    out = set()
    for r in range(1, len(s) + 1):
        for c in combinations(s, r):
            out.add(''.join(c))
    return sorted(out)

Пример:

>>> all_subsequences('HELLO')
['E', 'EL', 'ELL', 'ELLO', 'ELO', 'EO', 'H', 'HE', 'HEL', 'HELL', 'HELLO', 'HELO',
 'HEO', 'HL', 'HLL', 'HLLO', 'HLO', 'HO', 'L', 'LL', 'LLO', 'LO', 'O']
>>> all_subsequences('WORLD')
['D', 'L', 'LD', 'O', 'OD', 'OL', 'OLD', 'OR', 'ORD', 'ORL', 'ORLD', 'R', 'RD',
 'RL', 'RLD', 'W', 'WD', 'WL', 'WLD', 'WO', 'WOD', 'WOL', 'WOLD', 'WOR', 'WORD',
 'WORL', 'WORLD', 'WR', 'WRD', 'WRL', 'WRLD']
person kaya3    schedule 20.12.2019

arrow_upward
0
arrow_downward

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

from itertools import combinations_with_replacement

s = 'MISSISSIPPI'
lst = []

for i,j in combinations_with_replacement(range(len(s)), 2):
    if s[i:(j+1)] not in lst:
        lst.append(s[i:(j+1)]) # save new combination into list
        print(lst[-1]) # print new combination

Чтобы быть уверенным, что все случаи охвачены, очень полезно нарисовать комбинацию, по которой будет проходить петля. Предположим, что это общая строка, где буквы представлены их положением в списке Python, например, от 0 до 3.

Вот числа, сгенерированные "combinations_with_replacement"

00, 01, 02, 03,
11, 12, 13,
22, 23,
33

person marcmorin99    schedule 20.12.2019
comment
22 не является подпоследовательностью 0123. Кроме того, если вы используете его только для проверки принадлежности, используйте набор, а не список. Набор тестов на членство занимает O(1) раз. - person kaya3; 20.12.2019
comment
Разве это не все подстроки? Подпоследовательность — это последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка остальных элементов. - person DarrylG; 20.12.2019
comment
@kaya3 -- согласен. Но приведенный выше код создает подстроки, а не подпоследовательности (по крайней мере, когда я пробовал). Например, для sring cab результатом будет c, ca, cab, a, ab, b. - person DarrylG; 20.12.2019
comment
@DarrylG Верно, я неправильно понял ваш комментарий - приношу свои извинения. Да, вы правы, этот ответ создает подстроки, как это делает код OP; единственное отличие заключается в предотвращении дублирования. - person kaya3; 20.12.2019
comment
@kaya3 - нет проблем. Мне понравился (проголосовал) ваш ответ. - person DarrylG; 20.12.2019