Separando una cadena

Dada una cadena, quiero generar todas las combinaciones posibles. En otras palabras, todas las formas posibles de poner una coma en algún lugar de la cadena.

Por ejemplo:

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

Estoy un poco atascado en cómo generar todas las listas posibles. Las combinaciones solo me darán listas con la longitud del subconjunto del conjunto de cadenas, las permutaciones darán todas las formas posibles de ordenar.

Puedo hacer todos los casos con solo una coma en la lista debido a la iteración de los segmentos, pero no puedo hacer casos con dos comas como “ab”, “c”, “d” y “a”, “b” ,”discos compactos”

Mi bash w / slice:

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

¿Qué tal algo como:

 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 

después de lo cual:

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

Ciertamente, puede usar itertools para esto, pero creo que es más fácil escribir un generador recursivo directamente:

 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 

Entonces

 print list(gen_commas("abcd")) 

huellas dactilares

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

No estoy seguro de por qué encuentro esto más fácil. Tal vez solo porque es fácil hacerlo directamente 😉

Podría generar el conjunto de potencias de los n – 1 lugares donde podría poner comas:

¿Cuál es una buena manera de combinar a través de un conjunto?

y luego insertar comas en cada posición.

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

Da:

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

También una versión recursiva:

 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) 

Puede resolver el problema de la composición de enteros y usar las composiciones para guiar dónde dividir la lista. La composición de enteros se puede resolver con bastante facilidad con un poco de progtwigción dinámica.

 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) 

Otra forma de generar composición entera:

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