Create all subsets from string- recursively

Question

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]

You do not appear to have written *any* code of your own; please post what you have. — Scott Hunter, Jun 01 '20 at 11:44
Without recursion: https://stackoverflow.com/questions/28870709/python-every-possible-combination-of-a-string — NewPythonUser, Jun 01 '20 at 11:45
What exactly was the problem with the code you have written? — mkrieger1, Jun 01 '20 at 11:45
Does this answer your question? [Python every possible combination of a string](https://stackoverflow.com/questions/28870709/python-every-possible-combination-of-a-string) — Anwarvic, Jun 01 '20 at 11:46
@sK500 in this example, they are considered to be distinct characters, as I am trying to create subsets of all words from a string. Each entry counts. Maybe I didn't call it the correct way, rather I should have called it: Permutations with repetition. — Stan, Jun 01 '20 at 11:49
@Anwarvic no, it does not answer to my criteria of a recursive function. — Stan, Jun 01 '20 at 11:58
@NewPythonUser same here, not recursive and not a function. It's just a solution using python's moduls. — Stan, Jun 01 '20 at 11:58
Shouldn't the subset be: `['', 'a', 'b', 'ab']`? Why do you have 'aa', 'bb', and both 'ab' and 'ba'? — DarrylG, Jun 01 '20 at 12:00
@DarrylG yes, let me rename it- 'Permutations with repetition', and I have edited the set and output in the original question, — Stan, Jun 01 '20 at 12:05
@GáborFekete because this is the intention of the exercise, not just for fun :) — Stan, Jun 01 '20 at 12:09
@ScottHunter I have supplied a code now. Do you know how to fix it? — Stan, Jun 01 '20 at 12:15

Gábor Fekete · Answer 1 · 2020-06-01T12:53:24.053

1

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

edited Jun 01 '20 at 12:53

answered Jun 01 '20 at 12:22

Gábor Fekete

1,022
6
15

can you do it without passing on the i and r? meaning- only passing on the string itself? I know it's forced... – Stan Jun 01 '20 at 12:24
1

@Stan--for avoid passing i & r add a default for r: `def recursive_product(s,r=None,i=0): if r is None: r = []`. So now usage becomes: `print(recursive_product('ab'))` – DarrylG Jun 01 '20 at 12:49

score 0 · Answer 2 · answered Jun 01 '20 at 11:46

0

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

answered Jun 01 '20 at 11:46

Joshua Fox

17,144
15
75
126

thanks, But I was looking for a solution by defining a recursive function with only one input- the string. – Stan Jun 01 '20 at 11:53

Laurent B. · Answer 3 · 2020-06-06T06:09:04.447

import itertools as it

def all_subsets(iterable):
    s = list(iterable)
    subsets = it.chain.from_iterable(it.permutations(s,r) for r in range(len(s) + 1))
    return list(map("".join, list(subsets)))

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

print(all_subsets('abc'))
# ['', 'a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Create all subsets from string- recursively

3 Answers3