Взятие строки чисел и вставка + и – операторов
Я в тупике от этой, казалось бы, тривиальной проблемы …
Я хотел бы использовать python, чтобы взять строку чисел (например, "123" ) и создать список, в котором есть все возможные выражения, в которых между любыми числами могут быть вставлены "+" или "-" (или вообще ничего).
- Python cStringIO занимает больше времени, чем StringIO в письменной форме (производительность строковых методов)
- производительность элемента python слишком медленная
- Разделение строки с использованием разделителей пространства и максимальной длины
- Распечатайте символы «\ n» или новые символы как часть вывода на терминале
- Найти начальную и конечную позиции всех вхождений в строке в Python
Для примера "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
- Каков предпочтительный способ подсчета количества входов определенного символа в строке (Python)?
- Изменение строк в функциях Python
- Модуль подпроцесса Python намного медленнее команд (устарел)
- Возврат младшего индекса для первого символа без пробелов в строке в Python
- Проверка, может ли строка быть преобразована в float в Python
- Капитализация каждого предложения в строке в Python 3
- Javascript эквивалент rsplit Python
- Подсчет появления нескольких подстрок в панде
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 (ужасно) как в пространстве, так и в эффективности, если оно реализовано вслепую.