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

Я в тупике от этой, казалось бы, тривиальной проблемы …

Я хотел бы использовать 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 

3 Solutions collect form web for “Взятие строки чисел и вставка + и – операторов”

Вот немного хакерское, но короткое решение, использующее 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 

Я считаю, что рекурсивное решение действительно более чистое.

Это немного плотно, но 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] включен в конце.

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

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

  • Лучший способ петли над питонной строкой назад
  • По умолчанию замена% s в сценариях python
  • Изменить символ новой строки .readline () ищет
  • Как проверить, является ли str (переменная) пустым или нет?
  • почему строки python не имеют функции __iter__?
  • Добавить знаки умножения (*) между коэффициентами
  • Как извлечь URL-адрес из строки с помощью python?
  • Почему Python имеет функцию формата, а также метод форматирования
  • Получить декорированный объект функции по имени строки
  • Оптимизация покрытия строк в Python
  • Разбирая пустую строку в Python, почему split () возвращает пустой список в то время как split ('\ n') возвращает ?
  • Python - лучший язык программирования в мире.