Taking a string of numbers and inserting + and - operators

Question

I'm stumped by this seemingly trivial problem...

I would like to use python to take a string of numbers ("123" for example) and create a list that has all possible expressions where a "+" or "-" (or nothing at all) can be inserted between any numbers.

For the example "123" the list would be:

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

If the length of the string of numbers is N, then the list should contain 3^(N-1) strings.

I feel like this should be done recursively, but I'm stuck trying to figure out how to return the 3 different options (+,-,None).

I believe that the base case of the function should be:

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

Answer 1

Here's a slightly hacky, but short solution using 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]

Example:

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

And here's a recursive solution:

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

I think the recursive solution is indeed cleaner here.

Answer 2

It's a bit dense, but itertools is your friend here:

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 magic here is coming from the function product, which takes the right number of combinations with replacement (which could also be used). How do we know how many terms we need? It looks like you can only insert an operation between any two values of the expression, so we need len(expr)-1 values to insert. It's useful to look at the output of:

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

i.e. we get every combination by grabbing two elements from the list where order is important. The last print line in the answer is simply the glue that puts the two expression together, making sure that the last term expr[-1] is tacked on at the end.