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 ;-)
Podría generar el conjunto de potencias de los lugares n - 1 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.
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)