Взятие строки чисел и вставка + и - операторов

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 различных варианта (+, -, Нет).

Я считаю, что базовый вариант функции должен быть:

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

Answer 1

Вот немного хакерское, но короткое решение с использованием 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] в конце.

Answer 3

Разбейте его на рекурсивные подзадачи: для строки символьных индексов 0..N (включительно) берут 0 и 1, генерируют массив решений для символов 2..N рекурсивно (пусть этот массив будет A), получая другой массивгде каждая комбинация 0 и 1 (например, 01, 0 + 1 и т. д.) добавляется к каждому решению в A. Если не осталось больше символов, просто верните комбинации.

Обратите внимание, чтовышеприведенное описание, возможно, запускает O (бездонный) как в пространстве, так и в эффективности, если реализовано вслепую.