取一串数字并插入+和 - 运算符

Question

我被这个看似微不足道的问题困扰了......

我想使用python来获取一串数字("123"例如)并创建一个列表,其中包含所有可能的表达式,其中可以在任何数字之间插入"+"或"-"(或根本没有).

对于示例"123",列表将是:

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

如果数字串的长度为N,则列表应包含3 ^(N-1)个字符串.

我觉得这应该以递归的方式完成,但我不知道如何找出如何返回3个不同的选项(+, - ,None).

我相信函数的基本情况应该是:

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

Answer 1

这是一个有点hacky,但简短的解决方案使用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]

例:

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

这是一个递归解决方案:

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

我认为这里的递归解决方案确实更清晰.

Answer 2

它有点密集,但是itertools你的朋友在这里:

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

这里真正的魔力来自于该功能product,它采用了正确数量的替换组合(也可以使用).我们怎么知道我们需要多少个术语？看起来你只能在表达式的任意两个值之间插入一个操作,所以我们需要len(expr)-1插入值.查看以下输出是有用的:

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

即我们通过从列表中获取顺序很重要的两个元素来获得每个组合.答案中的最后一条打印线只是将两个表达式放在一起的胶水,确保最后一个术语在最后expr[-1]加上.