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

to the itertools commenter, what page? i'm looking through this http://docs.python.org/2/library/itertools.html but maybe this is the incorrect one to be searching through — Noob Coder, Dec 24 '13 at 04:35
There are 2^(n-1) possibilities (you missed `['a', 'bc', 'd']` in your example) because at each point in between letters, you could either split the string or not. — Karl Knechtel, Dec 24 '13 at 04:36

score 15 · Accepted Answer · answered Dec 24 '13 at 04:42

15

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

answered Dec 24 '13 at 04:42

DSM

342,061
65
592
494

1

+1 Why don't you simply `yield` it, instead of storing it in `split`? – thefourtheye Dec 24 '13 at 04:45
@thefourtheye: only 'cause I tend to work line by line, and I didn't realize I was deep enough to yield at the time. :^) You're right, of course, there's no need to bind a local to it. – DSM Dec 24 '13 at 04:47
its crazy to me how much is going on in this line: split = [s[i:j] for i,j in zip((0,)+c, c+(None,))], but i finally got it! – Noob Coder Dec 24 '13 at 05:08
@NoobCoder: yeah, that idiom is useful for taking a bunch of split locations and generating the corresponding sequences. – DSM Dec 24 '13 at 05:14

score 15 · Answer 2 · answered Dec 24 '13 at 04:48

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

Now try that on a really long string.. (I know, I know, don't tug on Superman's cape..) — DSM, Dec 24 '13 at 05:21

perreal · Answer 3 · 2013-12-24T05:02:27.297

3

Using itertools:

import itertools
input_str =  "abcd"
for k in range(1,len(input_str)):
    for subset in itertools.combinations(range(1,len(input_str)), k): 
        s = list(input_str)
        for i,x in enumerate(subset): s.insert(x+i, ",")
        print "".join(s)

Gives:

a,bcd
ab,cd
abc,d
a,b,cd
a,bc,d
ab,c,d
a,b,c,d

Also a recursive version:

def commatoze(s,p=1):
    if p == len(s):
        print s
        return
    commatoze(s[:p] + ',' + s[p:], p + 2)
    commatoze(s, p + 1)

input_str =  "abcd"
commatoze(input_str)

edited Dec 24 '13 at 05:02

answered Dec 24 '13 at 04:42

perreal

94,503
21
155
181

More options for generating the power set in a response to a previous question: http://stackoverflow.com/questions/1482308/whats-a-good-way-to-combinate-through-a-set – James King Dec 24 '13 at 04:46

score 3 · Answer 4 · edited May 23 '17 at 12:23

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.

edited May 23 '17 at 12:23

Community

1
1

answered Dec 24 '13 at 04:44

James King

6,229
3
25
40

Lie Ryan · Answer 5 · 2013-12-24T06:19:28.123

You can solve the integer composition problem and use the compositions to guide where to split the list. Integer composition can be solved fairly easily with a little bit of dynamic programming.

def composition(n):
    if n == 1: 
        return [[1]] 
    comp = composition (n - 1) 
    return [x + [1] for x in comp] + [y[:-1] + [y[-1]+1] for y in comp]

def split(lst, guide):
    ret = []
    total = 0
    for g in guide:
        ret.append(lst[total:total+g])
        total += g
    return ret

lst = list('abcd')
for guide in composition(len(lst)):
    print split(lst, guide)

Another way to generate integer composition:

from itertools import groupby
def composition(n):
    for i in xrange(2**(n-1)):
        yield [len(list(group)) for _, group in groupby('{0:0{1}b}'.format(i, n))]

score 0 · Answer 6 · answered Oct 09 '19 at 23:46

Given

import more_itertools as mit

Code

list(mit.partitions("abcd"))

Output

[[['a', 'b', 'c', 'd']],
 [['a'], ['b', 'c', 'd']],
 [['a', 'b'], ['c', 'd']],
 [['a', 'b', 'c'], ['d']],
 [['a'], ['b'], ['c', 'd']],
 [['a'], ['b', 'c'], ['d']],
 [['a', 'b'], ['c'], ['d']],
 [['a'], ['b'], ['c'], ['d']]]

Install more_itertools via > pip install more-itertools.

Separating a String

6 Answers6

Linked