Generate every possible subset of length 1..n of list/string

Question

Problem

I have a string, for which I want to find every possible subset of lengths 1..n.

Example

Given the string "abc" and n=3, I want to produce the following list:

{"a", "b", "c", "aa", "ab", "ac", "ba", ..., "aaa", "aab", "aac", "aba" ..., "ccc"}

My attempt

...is painfully novice. One loop for every n, nested n times.

For n = 3, I'd have:

characters = "abcdef" # and so on

for char in characters:
    print(char)

for char1 in characters:
    for char2 in characters:
        print(str(char1) + str(char2))

for char1 in characters:
    for char2 in characters:
        for char3 in characters:
            print(str(char1) + str(char2) + str(char3))

As you can see, this is unscalable to say the least. Is there a nice way to do this? Any complexity reductions would also be cool, although I have a hard time imagining any.

Answer 1

itertools.product is what you need. Use "".join" to join characters into a single string.

>>> import itertools
>>> n = 3
>>> s = "abc"
>>> for i in range(n):
    print(["".join(prod) for prod in itertools.product(s, repeat = i + 1)])


['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']