3

Not sure if this has been asked before, but couldn't find a specific mention of this type of problem.

This is a variant of subset sum and knapsack.

Although a similar question appears to have been asked before, but the logic is different enough to warrant a new thread.

Parameters : The total is given as well as a list of integers. The integers can be combined any number of ways (e.g. 1 2 3 = 12, 3 or 1, 23 or 1, 2 3) 3 operations are allowed :

  • 1 addition
  • 1 subtraction
  • 1 division

Sample :

1 2 9 3 7 4 = 22

Solution :

(129 - 3) / 7 + 4 = 22

Is there a classification for this type of exercise? (e.g. subset-sum, etc.)

Some thoughts :

  1. Create a multidimensional array of all possible number combinations. Since only 3 operators are allowed, the array would contain 3 columns/elements.

  2. Randomly insert the operators at points 1, 2 or 3 and brute-force until a solution is reached.

This is monumentally distant from an elegant solution.
Any insight would be appreciated.

I will probably code this in Perl, but pseudo code, pointers or syntax in any language would be great. Haughty sneering at my lack of mathematical wherewithal is also cool ;)

Thanks in advance!

2

2 Answers 2

1

I just answered this question, but it was incorrectly migrated to another stackexchange site: https://codegolf.stackexchange.com/questions/3019/getting-an-answer-from-a-string-of-digits/3027#3027

Is there a classification for this type of exercise? (e.g. subset-sum, etc.)

I would call it finding all the binary-operator "reductions" of a list, applied in arbitrary order, with the operators +, -, *, /, and 10a+b/concat


Here's a brute-force approach in python. At every node in the trees below, take the Cartesian product of the possibilities on the left and the right. For each pair, apply all operators to it, to produce a set of new possibilities. You have to be careful not to do (1-2)3 = -13; you can get around this issue by creating Digit objects.

Below is an illustration of Catalan numbers where each node is an operator. The number of operations will be roughly Catalan(#digits-1) * #operators^(#digits-1). If #digits=10 then it should only be about a billion things to try.

enter image description here

Using How to print all possible balanced parentheses for an expression? we can write:

#!/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)))
1
  • Thanks! Very much appreciated. Will try to implement and rewrite for this specific scenario later today.
    – Methods
    Jul 8, 2011 at 14:51
0

A simple brute-force approach that seems to work quite well.

Let's use RPN to avoid parenthesis. Split the input into single digits and try inserting operators (which are: nothing, space and arithmetic operators) in between digits until the resulting string evaluates to the target value.

An illustration in javascript: http://jsfiddle.net/B5NdN/4 . I simply loop from 0 to 6^(input length) to obtain all possible operators' combinations there, your task may require something more sophisticated, but the principle remains.

1
  • Great food for thought, thanks a lot. Hadn't thought of / wasn't familiar with RPN.
    – Methods
    Jul 8, 2011 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.