CODEWITHSUNDEEP
pythonpermutationpython-itertools
Noob Coder
Noob Coder

Reputation: 949

Separating a String

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

Upvotes: 23

Views: 1063

Answers (6)

pylang
pylang

Reputation: 44515

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.

Upvotes: 0

Lie Ryan
Lie Ryan

Reputation: 64845

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

Upvotes: 1

perreal
perreal

Reputation: 97948

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)

Upvotes: 3

Tim Peters
Tim Peters

Reputation: 70602

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

Upvotes: 15

James King
James King

Reputation: 6365

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.

Upvotes: 3

DSM
DSM

Reputation: 353099

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

Upvotes: 15

Related Questions