Tomando una serie de números y la inserción de + y - los operadores

Question

Estoy confundido por este problema aparentemente trivial ...

me gustaría utilizar Python para tomar una serie de números ("123" por ejemplo) y crear una lista que tiene todas las expresiones posibles donde se puede insertar un "+" o "-" (o nada en absoluto) entre cualquier número.

Para el ejemplo "123" la lista sería:

["123","12+3","12-3","1+23","1+2+3","1+2-3","1-23","1-2+3","1-2-3"] 

Si la longitud de la cadena de números es N, entonces la lista debe contener 3^(n-1) cadenas.

Siento que esto debería hacerse de forma recursiva, pero estoy atascado tratando de encontrar la forma de devolver las 3 opciones diferentes (+, -, Ninguno).

creo que el caso base de la función debe ser:

def options(string): 
    if len(string) == 1: 
    return string 
    else: 
    #This is where I am stuck 

Answer 1

Aquí es una solución poco hacky, pero corto usando itertools.product():

def plus_minus(s): 
    for t in itertools.product(["", "+", "-"], repeat=len(s) - 1): 
     yield "".join(itertools.chain.from_iterable(zip(s, t))) + s[-1] 

Ejemplo:

>>> list(plus_minus("123")) 
['123', '12+3', '12-3', '1+23', '1+2+3', '1+2-3', '1-23', '1-2+3', '1-2-3'] 

Y he aquí una solución recursiva:

def plus_minus(s): 
    if len(s) <= 1: 
     yield s 
     return 
    for x in ["", "+", "-"]: 
     for y in plus_minus(s[1:]): 
      yield s[0] + x + y 

Creo que la solución recursiva es de hecho más limpio aquí.

Answer 2

Es un poco denso, pero itertools es su amigo aquí:

import itertools as itr 
ops = ["+","-",""] 
expr = "123" 
vals = itr.product(ops,repeat=len(expr)-1) 
print [''.join([x+y for x,y in zip(expr,v)])+expr[-1] for v in vals] 

[ '1 + 2 + 3 ',' 1 + 2-3 ',' 1 + 23 ',' 1-2 + 3 ',' 1-2-3 ',' 1-23 ', '12 +3', '12 -3 ' , '123']

The real ma gic aquí viene de la función product, que toma el número correcto de combinaciones con reemplazo (que también podría usarse). ¿Cómo sabemos cuántos términos necesitamos? Parece que solo puede insertar una operación entre dos valores de la expresión, por lo que necesitamos valores len(expr)-1 para insertar. Es útil observar en la salida de:

list(itr.product([1,3,5],repeat=2)) 

[(1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)]

es decir, obtenemos cada combinación al tomar dos elementos de la lista donde el orden es importante. La última línea de impresión en la respuesta es simplemente el pegamento que junta las dos expresiones, asegurándose de que el último término expr[-1] se haya añadido al final.

Answer 3

Divídalo en subproblemas recursivos: para una cadena de índices de caracteres 0..N (inclusive) tome 0 y 1, genere una matriz de soluciones para los caracteres 2..N recursivamente (deje que esta matriz sea A), produciendo otra array donde cada combinación de 0 y 1 (por ejemplo, 01, 0 + 1, etc.) se antepone a cada solución en A. Si no quedan más caracteres, simplemente devuelva las combinaciones.

Sin embargo, tenga en cuenta que la descripción anterior posiblemente se ejecute O (abismal) tanto en el espacio como en la eficiencia si se implementa a ciegas.