以一串數字和插入+和 - 運營商

我想用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個不同的選項（+， - ，無）。

我認爲，功能的基本情況應該是：

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

來源

2012-03-22 Dream Lane

下面是使用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

我覺得遞歸解決方案這裏確實很乾淨。

來源

2012-03-22 14:10:22

優秀的解決方案！謝謝 – 2012-03-22 14:51:36

這是一個有點遲鈍，但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']

真正的ma這裏的gic來自功能product，它採用了正確數量的組合與替換（也可以使用）。我們如何知道我們需要多少條款？它看起來像只能在表達式的任何兩個值之間插入操作，所以我們需要插入len(expr)-1值。

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

[（1,1），（1,3），（1,5），（3,1），（3,3），（：它看的輸出是有用（5,1），（5,3），（5,5）]

即我們從列表中獲取每個組合的順序是重要的。答案中的最後一行打印只是將兩個表達式放在一起的粘合劑，確保最後一個術語expr[-1]已結束。

來源

2012-03-22 14:10:06 Hooked

我很喜歡這個答案，謝謝。 +1 – 2012-03-22 14:51:03

將其分解爲遞歸子問題：對於字符索引0..N（含）的字符串取0和1，爲字符2..N遞歸地生成一個數組解決方案（讓該數組爲A），產生另一個數組，其中0和1的每個組合（例如01,0 + 1等）都預置在A中的每個解決方案中。如果沒有剩餘的字符，則返回組合。

但請注意，如果盲目實施，上述描述可能會在空間和效率上運行O（糟糕）。

來源

2012-03-22 14:17:02 milliburn

以一串數字和插入+和 - 運營商

回答

相關問題