Cant solve php algorithm with variations

Question

I have to find all possible solution from given sequence of integers that is equal to given number.

for example: 1,2,3,4,5,6,7,8,9 that is equal to 100 answer: 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100

My solution is for another sum in the example 25:

$arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
$n = count($arr);
$sum = 25;

function checkSol() {
    global $arr;
    global $n;
    global $sum;
    $tempSum = 0;
    for ($i = 0; $i < $n; $i++) {
        $tempSum += $arr[$i];
    }

    if ($tempSum == $sum) {
        for ($i = 0; $i < $n; $i++) {
            if ($arr[$i] > 0) {
                printf("+%d ", $arr[$i]);
            } else {
                printf("%d ", $arr[$i]);
            }
        }
        printf(" = %d\n", $tempSum);
        echo "<br/>";
    }
}

function variate($i = 0) {
    global $arr;
    global $n;
    if ($i >= $n) {
        checkSol();
        return;
    }

    $arr[$i] = abs($arr[$i]);
    variate($i + 1);
    $arr[$i] = -abs($arr[$i]);
    variate($i + 1);
}

variate();

This is the result:

+1 +2 +3 -4 +5 -6 +7 +8 +9 = 25 
+1 +2 -3 +4 +5 +6 -7 +8 +9 = 25 
+1 -2 +3 +4 +5 +6 +7 -8 +9 = 25 
+1 -2 -3 +4 -5 +6 +7 +8 +9 = 25 
-1 +2 +3 +4 +5 +6 +7 +8 -9 = 25 
-1 +2 +3 -4 -5 +6 +7 +8 +9 = 25 
-1 +2 -3 +4 +5 -6 +7 +8 +9 = 25 
-1 -2 +3 +4 +5 +6 -7 +8 +9 = 25 
-1 -2 -3 -4 +5 +6 +7 +8 +9 = 25 

The real problem here is that I cant concat all posible variation like the example in the begining. Thanks in advance.

Answer 1

Edit: Credit to @m69 for the massive simplification.

Your problem can be attacked with concepts taken from Stars and bars.

We first need to look at your example to get an idea of how these concepts apply. We have the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9 and a solution 1 + 23 - 4 + 56 + 7 + 8 + 9. We note that order matters if we consider the mathematical definition of a sequence, so we will not need to consider permutations of the numbers themselves. Let’s look at your sequence through the lens of stars and bars:

1    2    3    4    5    6    7    8    9
   |   |    |    |     |    |    |    |    <<-- This is where either +, -, or a space will go

We need to fit all permutations of the vector (“+”, “-“, “”) where the bars occur. This means we have to generate all permutations with repetition of length 8. Once we insert these symbols in between (i.e. the bars above) the numbers in our sequence, we can finally evaluate the string.

Here is quick demonstration of the algorithm for generating permutations with repetition in C++. It is straightforward and should be easy to convert (here is a working example):

void permsWithRep(std::vector<int> v, int r) {

    int n = v.size();
    int r1 = r - 1, n1 = n - 1;
    std::vector<int> z(r, 0);
    int numRows = (int) std::pow(n, r);

    for (int i = 0; i < numRows; ++i) {
        for (int j = 0; j < r; ++j)
            std::cout << v[z[j]] << ' ';
        std::cout << std::endl;

        for (int k = r1; k >= 0; --k) {
            if (z[k] != n1) {
                ++z[k];
                break;
            } else {
                z[k] = 0;
            }
        }
    }
}

In order to insert our symbols efficiently, we need to augment our original sequence with empty slots between each number like so:

1,  , 2,  , 3,  , 4,  , 5,  , 6,  , 7,  , 8,  , 9

Now we can insert our permutation of symbols in the empty slots. E.g. :

1,"+", 2,"-", 3,"", 4,"", 5,"", 6,"", 7,"", 8,"", 9

Next, we collapse the vector and evaluate:

1 + 2 - 3456789  <<-- collapse
-3456786    <<-- evaluate

Here is the code in full using R and the package RcppAlgos (I am the author) which is written in C++:

getSolutions <- function(v, target, myOps = c("+", "-", "")) {
    n <- length(v)
    permExp <- RcppAlgos::permuteGeneral(myOps, n - 1, 
                                         repetition = TRUE)
    vEval <- vector(length = 2*n - 1)

    ## augmenting original sequence to create slot for symbols
    vEval[seq(1, 2*n - 1, 2)] <- v

    lapply(1:nrow(permExp), function(y) {

        ## insert symbols in empty slots
        vEval[seq(2, 2*n - 2, 2)] <- permExp[y, ]

        ## collapse and evaluate
        test <- eval(parse(text = paste0(vEval, collapse = "")))
        if (test == target)
            print(paste0(vEval, collapse = ""))
        test
    })
}

And here is a demonstration:

test100 <- getSolutions(1:9, 100)
[1] "1+2+3-4+5+6+78+9"
[1] "1+2+34-5+67-8+9"
[1] "1+23-4+5+6+78-9"
[1] "1+23-4+56+7+8+9"     <<-- example given by OP
[1] "12+3+4+5-6-7+89"
[1] "12+3-4+5+67+8+9"
[1] "12-3-4+5-6+7+89"
[1] "123+4-5+67-89"
[1] "123+45-67+8-9"
[1] "123-4-5-6-7+8-9"
[1] "123-45-67+89"

Finally, since there are no restrictions on which operations can be used, we have to think about other possible ways of getting our target value. The solution above is easily extended to more general cases. Let’s say we want to add multiplication to the mix. No problem:

testFourSymbols <- getSolutions(1:9, 100, c("*", "-", "+", ""))
[1] "1*2*3*4+5+6+7*8+9"
[1] "1*2*3*4+5+6-7+8*9"
[1] "1*2*3*4-5-6+78+9"
[1] "1*2*3+4+5+6+7+8*9"
[1] "1*2*3-4*5+6*7+8*9"
[1] "1*2*3-4+5+6+78+9"
[1] "1*2*3-45+67+8*9"
[1] "1*2*34+56-7-8-9"
[1] "1*2+3*4+5-6+78+9"
[1] "1*2+3+4*5+6+78-9"
[1] "1*2+3+45+67-8-9"
[1] "1*2+3-4+5*6+78-9"
[1] "1*2+34+5+6*7+8+9"
[1] "1*2+34+5-6+7*8+9"
[1] "1*2+34+5-6-7+8*9"
[1] "1*2+34+56+7-8+9"
[1] "1*2-3+4*5-6+78+9"
[1] "1*2-3+4-5+6+7+89"
[1] "1*23+4+5+67-8+9"
[1] "1*23-4+5-6-7+89"
[1] "1*234+5-67-8*9"
[1] "1+2*3+4*5-6+7+8*9"
[1] "1+2*3+4+5+67+8+9"
[1] "1+2*3-4-5+6+7+89"
[1] "1+2*34-56+78+9"
[1] "1+2+3*4-5-6+7+89"
[1] "1+2+3+4+5+6+7+8*9"
[1] "1+2+3-4*5+6*7+8*9"
[1] "1+2+3-4+5+6+78+9"
[1] "1+2+3-45+67+8*9"
[1] "1+2+34*5+6-7-8*9"
[1] "1+2+34-5+67-8+9"
[1] "1+2-3*4+5*6+7+8*9"
[1] "1+2-3*4-5+6*7+8*9"
[1] "1+23*4+5-6+7-8+9"
[1] "1+23*4-5+6+7+8-9"
[1] "1+23-4+5+6+78-9"
[1] "1+23-4+56+7+8+9"
[1] "1+23-4-5+6+7+8*9"
[1] "1+234-56-7-8*9"
[1] "1-2*3+4*5+6+7+8*9"
[1] "1-2*3-4+5*6+7+8*9"
[1] "1-2*3-4-5+6*7+8*9"
[1] "1-2+3*4*5+6*7+8-9"
[1] "1-2+3*4*5-6+7*8-9"
[1] "1-2+3*4+5+67+8+9"
[1] "1-2+3+45+6+7*8-9"
[1] "1-2-3+4*5+67+8+9"
[1] "1-2-3+45+6*7+8+9"
[1] "1-2-3+45-6+7*8+9"
[1] "1-2-3+45-6-7+8*9"
[1] "1-2-34+56+7+8*9"
[1] "1-23+4*5+6+7+89"
[1] "1-23-4+5*6+7+89"
[1] "1-23-4-5+6*7+89"
[1] "12*3-4*5+67+8+9"
[1] "12*3-4+5-6+78-9"
[1] "12*3-4-5-6+7+8*9"
[1] "12+3*4+5+6+7*8+9"
[1] "12+3*4+5+6-7+8*9"
[1] "12+3*4-5-6+78+9"
[1] "12+3*45+6*7-89"
[1] "12+3+4+5-6-7+89"
[1] "12+3-4+5+67+8+9"
[1] "12+34+5*6+7+8+9"
[1] "12+34-5+6*7+8+9"
[1] "12+34-5-6+7*8+9"
[1] "12+34-5-6-7+8*9"
[1] "12-3+4*5+6+7*8+9"
[1] "12-3+4*5+6-7+8*9"
[1] "12-3-4+5*6+7*8+9"
[1] "12-3-4+5*6-7+8*9"
[1] "12-3-4+5-6+7+89"
[1] "123+4*5-6*7+8-9"
[1] "123+4-5+67-89"
[1] "123+45-67+8-9"
[1] "123-4-5-6-7+8-9"
[1] "123-45-67+89"

I know the code wasn't in php, but hopefully the ideas presented here will help you understand how to attack your problem.