CODEWITHSUNDEEP
pythoncombinationssubsequence
challenger
challenger

Reputation: 23

finding all possible subsequences in a given string

I have written this piece of code and it prints all substrings of a given string but I want it to print all the possible subsequences.

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)])

Upvotes: 0

Views: 8979

Answers (2)

kaya3
kaya3

Reputation: 51034

Use combinations to get subsequences. That's what combinations is for.

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)

Example:

>>> 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']

Upvotes: 6

marcmorin99
marcmorin99

Reputation: 9

One simple way to do so is to verify if the list you are making already has the case that you are iterating over. If you have already seen it, then skip it, if not, then append it to your list of seen combinations.

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

To be sure that all cases are covered, it really helps to make a drawing of combination that the loop will go over. Suppose a generic string, where letters are represented by their position in the python list, for example 0 to 3.

Here are the numbers generated by "combinations_with_replacement"

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

Upvotes: 0

Related Questions