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_repla

Solution 1:

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

from itertools import combinations

defall_subsequences(s):
    out = set()
    for r inrange(1, len(s) + 1):
        for c in combinations(s, r):
            out.add(''.join(c))
    returnsorted(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']

Solution 2:

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