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 can't concat all posible variation like the example in the begining.

That's a nice one. Don't see this complexity everyday here. Well, the real problem is that the amount of combinations that can give you a sum can be exhaustively big. You are most certainly headed into timing out your script considering the sum you might want to try. — Rafael
– Rafael, Commented Aug 29, 2018 at 9:25
You can use my solution as answer in stackoverflow.com/questions/50240628/… to get permutation and then check the sum equal to 100 / 25 — dWinder
– dWinder, Commented Aug 29, 2018 at 9:40
@Rafael The number of permutations isn't vary large at all. The sequence 123456789 has only eight intervals (1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8 and 8-9). In each interval, you have three options (+, - or the empty string), so the total number of permutations is 3^8, which is 6561. These can easily be tested in a fraction of a second. — r3mainer
– r3mainer, Commented Aug 29, 2018 at 12:48
In that case you are considering that the permutations occur in a sequence, @Squeamish, but considering the grade of the task, I would not assume that it is so simple as that. Considering that he wanted all the combinations of plus/minus from numbers that could be like: 91, 38, 42, 75, 6. If you consider the numbers concatenating inside the array, I would consider also any combination from this numbers. — Rafael
– Rafael, Commented Aug 29, 2018 at 12:59
And that is, of course, not even considering that the intervals might be of more than 2 digits. 123−45−6+7+9+8 = 96 for example is not equal to 100 but should be taken in consideration before summing everything. Unless it's stated that the permutations should have maximum two digits, I would say it's oversimplification to assume so. — Rafael
– Rafael, Commented Aug 29, 2018 at 13:33

Joseph Wood · Accepted Answer · 2018-08-30 13:21:55Z

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.

@m69 , I’m a bit embarrassed right now. Your method boils down to permutations of 3 elements with repeats of length 8. Way easier.
@m69, done. Thanks for making sure the community didn't have to suffer through the previous non-sense.

Collectives™ on Stack Overflow

Cant solve php algorithm with variations

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related