serial separate separar parse how getvalue example datos python permutation itertools

python - separate - Separando una cadena



split string arduino (5)

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



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


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)