Существует ли классификация для этого типа упражнения?(например, подмножество-сумма и т., *, / и 10a+b / concat
Вот подход грубой силы в python.В каждом узле деревьев внизу возьмите декартово произведение возможностей слева и справа.Для каждой пары примените к ней все операторы, чтобы создать набор новых возможностей.Вы должны быть осторожны, чтобы не делать (1-2)3 = -13;Вы можете обойти эту проблему, создав объекты Digit.
Ниже приведена иллюстрация каталонских чисел, где каждый узел является оператором.Количество операций будет примерно Catalan(#digits-1) * #operators^(#digits-1).Если #digits=10, то нужно попробовать только около миллиарда.
Использование Как вывести все возможные сбалансированные скобки для выражения?можно написать:
#!/usr/bin/python3
import operator as op
from fractions import Fraction
Fraction.__repr__ = lambda self: '{}/{}'.format(self.numerator, self.denominator)
Digits = tuple
operators = {op.add, op.sub, op.mul, Fraction}
def digitsToNumber(digits):
"""
(1,2,3) -> 123
123 -> 123
"""
if isinstance(digits, Digits):
return sum(d * 10**i for i,d in enumerate(reversed(digits)))
else: # is int or float
return digits
def applyOperatorsToPossibilities(left, right):
"""
Takes every possibility from the left, and every
possibility from the right, and takes the Cartesian
product. For every element in the Cartesian product,
applies all allowed operators.
Returns new set of merged possibilities, ignoring duplicates.
"""
R = set() # subresults
def accumulate(n):
if digitsToNumber(n)==TO_FIND:
raise Exception(n)
else:
R.add(n)
for l in left:
for r in right:
if isinstance(l, Digits) and isinstance(r, Digits):
# (1,2),(3) --> (1,2,3)
accumulate(l+r)
for op in operators:
# 12,3 --> 12+3,12-3,12*3,12/3
l = digitsToNumber(l)
r = digitsToNumber(r)
try:
accumulate(op(l,r))
except ZeroDivisionError:
pass
return R
def allReductions(digits):
"""
allReductions([1,2,3,4])
[-22, -5, -4, -3, -5/2, -1/1, -1/3, 0, 1/23, 1/6, 1/5, 1/3, 2/3, 1/1, 3/2, 5/3, 2, 7/2, 4/1, 5, 6, 7, 9, 15, 23, 24, 36, 123]
"""
for reduction in set.union(*associations(
digits,
grouper=applyOperatorsToPossibilities,
lifter=lambda x:{(x,)})
):
yield digitsToNumber(reduction)
TO_FIND = None
INPUT = list(range(1,4))
print(sorted(allReductions(INPUT)))