Zeichenfolge trennen

Question

Bei einer gegebenen Zeichenfolge möchte ich alle möglichen Kombinationen generieren. Mit anderen Worten, alle möglichen Wege, ein Komma irgendwo in die Zeichenfolge zu setzen.

Zum Beispiel:

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

Ich bin ein bisschen stecken, wie alle möglichen Listen zu generieren. Kombinationen geben mir nur Listen mit der Länge einer Teilmenge der Menge von Strings, Permutationen werden alle möglichen Arten der Ordnung geben.

Ich kann alle Fälle mit nur einem Komma in der Liste wegen der Iteration durch die Scheiben machen, aber ich kann Fälle mit zwei Kommas wie "ab", "c", "d" und "a" nicht machen , "b", "cd"

Mein Versuch w/Scheibe:

test="abcd" 

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

Answer 1

Wie wäre es so etwas wie:

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 

wonach:

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

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

Gibt:

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

auch eine rekursive 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) 

Answer 3

Sie konnten die Potenzmenge der n erzeugen - 1 Orte, die Sie Kommas setzen könnten:

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

und dann an jeder Position Kommas einfügen.

Answer 4

Sie können sicher itertools für diese, aber ich denke, es ist einfacher, direkt einen rekursiven Generator zu schreiben:

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 

Dann

print list(gen_commas("abcd")) 

druckt

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

Ich bin nicht sicher warum Ich finde das einfacher. Vielleicht, weil es einfach einfach ist, es direkt zu tun ;-)

Answer 5

Sie können die integer composition problem lösen und die Zusammensetzungen verwenden, um zu führen, wo die Liste aufgeteilt werden soll. Ganzzahlige Kompositionen lassen sich relativ einfach mit ein wenig dynamischer Programmierung lösen.

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) 

Eine weitere Möglichkeit, integer Zusammensetzung zu erzeugen:

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