# Getting all combinations of a string and its substrings

Posted on

### Question :

Getting all combinations of a string and its substrings

I’ve seen many questions on getting all the possible substrings (i.e., adjacent sets of characters), but none on generating all possible strings including the combinations of its substrings.

For example, let:

``````x = 'abc'
``````

I would like the output to be something like:

``````['abc', 'ab', 'ac', 'bc', 'a', 'b', 'c']
``````

The main point is that we can remove multiple characters that are not adjacent in the original string (as well as the adjacent ones).

Here is what I have tried so far:

``````def return_substrings(input_string):
length = len(input_string)
return [input_string[i:j + 1] for i in range(length) for j in range(i, length)]

print(return_substrings('abc'))
``````

However, this only removes sets of adjacent strings from the original string, and will not return the element `'ac'` from the example above.

Another example is if we use the string `'abcde'`, the output list should contain the elements `'ace'`, `'bd'` etc.

You can do this easily using `itertools.combinations`

``````>>> from itertools import combinations
>>> x = 'abc'
>>> [''.join(l) for i in range(len(x)) for l in combinations(x, i+1)]
['a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
``````

If you want it in the reversed order, you can make the `range` function return its sequence in reversed order

``````>>> [''.join(l) for i in range(len(x),0,-1) for l in combinations(x, i)]
['abc', 'ab', 'ac', 'bc', 'a', 'b', 'c']
``````

This is a fun exercise. I think other answers may use itertools.product or itertools.combinations. But just for fun, you can also do this recursively with something like

``````def subs(string, ret=['']):
if len(string) == 0:
return ret
ret = ret + list(map(lambda x: x+head, ret))
return subs(tail, ret)

subs('abc')
# returns ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
``````

@Sunitha answer provided the right tool to use. I will just go and suggest an improved way while using your `return_substrings` method. Basically, my solution will take care of duplicates.

I will use `"ABCA"` in order to prove validity of my solution. Note that it would include a duplicate `'A'` in the returned list of the accepted answer.

Python 3.7+ solution,

``````x= "ABCA"
def return_substrings(x):
all_combnations = [''.join(l) for i in range(len(x)) for l in combinations(x, i+1)]
return list(reversed(list(dict.fromkeys(all_combnations))))
# return list(dict.fromkeys(all_combnations)) for none-reversed ordering

print(return_substrings(x))
>>>>['ABCA', 'BCA', 'ACA', 'ABA', 'ABC', 'CA', 'BA', 'BC', 'AA', 'AC', 'AB', 'C', 'B', 'A']
``````

Python 2.7 solution,

You’ll have to use `OrderedDict` instead of a normal `dict`. Therefore,

`````` return list(reversed(list(dict.fromkeys(all_combnations))))
``````

becomes

``````return list(reversed(list(OrderedDict.fromkeys(all_combnations))))
``````

Order is irrelevant for you ?

You can reduce code complexity if order is not relevant,

``````x= "ABCA"
def return_substrings(x):
all_combnations = [''.join(l) for i in range(len(x)) for l in combinations(x, i+1)]
return list(set(all_combnations))
``````

``````def return_substrings(s):
all_sub = set()
recent = {s}

while recent:
tmp = set()
for word in recent:
for i in range(len(word)):