Generate all substrings(in lexicographic order)of given string in alphabetical order

Question

I recently saw this problem and am really stuck at implementing it.

The problem is to generate all possible alphabetically ordered substrings from given string.

Smaller Example : For string xcv

I am required to generate the output :

c cv cvx v vx x

Bigger Example : For the string hgrte

I am required to generate the following substrings :

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

This is my implementation which didn't produce the desired output.

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

This is the output of my code :

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

I know I have to use backtracking and recursion after printing eghrt, but I am really stuck at implementing it. Thanks in advance :)

Probably in the smaller example several combinations are missing (cxv, vcx, vxc etcetera). Aren't they? — Roberto Caboni, Mar 28 '20 at 13:50
No, the alphabets should be in their lexicographic order in the substrings, sorry I will add the constraint to my question. Thanks :) — Suraj, Mar 28 '20 at 13:51

score 1 · Accepted Answer · answered Mar 28 '20 at 14:49

1

You can iterate through the different lengths and use itertools.combinations to produce the combinations of letters:

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

answered Mar 28 '20 at 14:49

blhsing

91,368
6
71
106

Your a genius, great stuff, can you include some explanation if possible, thanks a lot :) – Suraj Mar 28 '20 at 14:52
1

Understood it, as you told `combinations` is to produce strings of different lengths and we sort these words in the list. – Suraj Mar 28 '20 at 18:16

score 1 · Answer 2 · answered Mar 28 '20 at 15:14

1

You could do it without recursion, if recursion isn't an explicit requirement:

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)

The powerset function taken from How to get all subsets of a set? (powerset)

answered Mar 28 '20 at 15:14

Błotosmętek

12,717
19
29

1

Have you used `list` as a variable name somewhere in your code? Then you've overwritten the built-in `list` function. DON'T. – Błotosmętek Mar 28 '20 at 15:43
Yes, am sorry ! Your code is easier to understand, thanks a lot ! – Suraj Mar 28 '20 at 15:45

score 0 · Answer 3 · answered Mar 28 '20 at 14:48

0

You forgot to consider non-consecutive sub-strings. An easy way to do this is with 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)])))

That will do the job. If you prefer to not use the standard library, you can use bit masking to obtain all possible sub-strings.

answered Mar 28 '20 at 14:48

iranrmrf

1
1

There's no reason to use a set here. – blhsing Mar 28 '20 at 14:51

score 0 · Answer 4 · answered May 25 '22 at 08:06

s = 'abc'
n = len(s)
p = 2 ** n   # total number of power sets 
res = []
for i in range(1, p):
    tmp = ''
    for j in range(n):
        if i & (1 << j):
            tmp += s[j]
    res.append(tmp)

print(sorted(res))   # ['a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']


# Time Complexity: O(2^n * n)
# Space Complexity: O(n)

Generate all substrings(in lexicographic order)of given string in alphabetical order

4 Answers4