Separating a String

Question

Given a string, I want to generate all possible combinations. In other words, all possible ways of putting a comma somewhere in the string.

For example:

input:  ["abcd"]
output: ["abcd"]
        ["abc","d"]
        ["ab","cd"]
        ["ab","c","d"]
        ["a","bc","d"]
        ["a","b","cd"]
        ["a","bcd"]
        ["a","b","c","d"]

I am a bit stuck on how to generate all the possible lists. Combinations will just give me lists with length of subset of the set of strings, permutations will give all possible ways to order.

I can make all the cases with only one comma in the list because of iterating through the slices, but I can't make cases with two commas like "ab","c","d" and "a","b","cd"

My attempt w/slice:

test="abcd"

for x in range(len(test)):
     print test[:x],test[x:]

Answer 1

How about something like:

from itertools import combinations

def all_splits(s):
    for numsplits in range(len(s)):
        for c in combinations(range(1,len(s)), numsplits):
            split = [s[i:j] for i,j in zip((0,)+c, c+(None,))]
            yield split

after which:

>>> for x in all_splits("abcd"):
...     print(x)
...     
['abcd']
['a', 'bcd']
['ab', 'cd']
['abc', 'd']
['a', 'b', 'cd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

Answer 2

You can certainly use itertools for this, but I think it's easier to write a recursive generator directly:

def gen_commas(s):
    yield s
    for prefix_len in range(1, len(s)):
        prefix = s[:prefix_len]
        for tail in gen_commas(s[prefix_len:]):
            yield prefix + "," + tail

Then

print list(gen_commas("abcd"))

prints

['abcd', 'a,bcd', 'a,b,cd', 'a,b,c,d', 'a,bc,d', 'ab,cd', 'ab,c,d', 'abc,d']

I'm not sure why I find this easier. Maybe just because it's dead easy to do it directly ;-)

Answer 3

You could generate the power set of the n - 1 places that you could put commas:

what's a good way to combinate through a set?

and then insert commas in each position.