CODEWITHSUNDEEP
pythonpython-2.7recursion
Stan
Stan

Reputation: 151

Create all subsets from string- recursively

I am trying to create all subset of a given string recursively. Given string = 'aab', we generate all subsets for the characters being distinct. The answer is: ["", "b", "a", "ab", "ba", "a", "ab", "ba", "aa", "aa", "aab", "aab", "aba", "aba", "baa", "baa"]. I have been looking at several solutions such as this one but I am trying to make the function accept a single variable- only the string and work with that, and can't figure out how. I have been also looking at this solution of a similar problem, but as it deals with lists and not strings I seem to have some trouble transforming that to accept and generate strings. Here is my code, in this example I can't connect the str to the list. Hence my question. I edited the input and the output.

def gen_all_strings(word):

    if len(word) == 0:
        return ''

    rest = gen_all_strings(word[1:])

    return  rest + [[ + word[0]] + dummy for dummy in rest]

Upvotes: 1

Views: 537

Answers (3)

Laurent B.
Laurent B.

Reputation: 2263

import itertools as it

s='aab'
subsets = sorted(list(map("".join, it.chain.from_iterable(it.permutations(s,r) for r in range(len(s) + 1)))))

print(subsets)
# ['', 'a', 'a', 'aa', 'aa', 'aab', 'aab', 'ab', 'ab', 'aba', 'aba', 'b', 'ba', 'ba', 'baa', 'baa']

Upvotes: 0

Gábor Fekete
Gábor Fekete

Reputation: 1358

from itertools import *

def recursive_product(s,r=None,i=0):
    if r is None:
        r = []
    if i>len(s):
        return r
    for c in product(s, repeat=i):
        r.append("".join(c))
    return recursive_product(s,r,i+1)

print(recursive_product('ab'))
print(recursive_product('abc'))

Output:

['', 'a', 'b', 'aa', 'ab', 'ba', 'bb']

['', 'a', 'b', 'c', 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc', 'aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

To be honest it feels really forced to use recursion in this case, a much simpler version that has the same results:

nonrecursive_product = lambda s: [''.join(c)for i in range(len(s)+1) for c in product(s,repeat=i)]

Upvotes: 1

Joshua Fox
Joshua Fox

Reputation: 19655

This is the powerset of the set of characters in the string.

from itertools import chain, combinations

s = set('ab') #split string into a set of characters

# combinations gives the elements of the  powerset of a given length r
# from_iterable puts all these into an 'iterable'
# which is converted here to a list

list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))

Upvotes: 0

Related Questions