Не могу решить алгоритм php с вариациями

Обновлено: Кредит @ m69 за огромное упрощение.

Ваша проблема может быть решена с помощью концепций, взятых из Звезды и полосы.

Сначала нам нужно взглянуть на ваш пример, чтобы понять, как применяются эти концепции. У нас есть последовательность 1, 2, 3, 4, 5, 6, 7, 8, 9 и решение а1 + 23 - 4 + 56 + 7 + 8 + 9. Отметим, что порядок имеет значение, если мы рассматриваем математическое определение последовательности, поэтому нам не нужно рассматривать перестановки самих чисел. Давайте посмотрим на вашу последовательность через призму звезд и полос:

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

Нам нужно подогнать все перестановки вектора (“+”, “-“, “”), где встречаются полосы. Это означает, что мы должны сгенерировать все перестановки с повторением длины 8. После того, как мы вставим эти символы между (т. Е. Столбцы выше) числами в нашей последовательности, мы, наконец, сможем оценить строку.

Вот быстрая демонстрация алгоритма генерации перестановок с повторением в C++. Это просто и должно быть легко преобразовано (здесь - рабочий пример):

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;
            }
        }
    }
}

Чтобы эффективно вставить наши символы, нам нужно дополнить нашу исходную последовательность пустыми слотами между каждым числом, например:

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

Теперь мы можем вставить нашу перестановку символов в пустые слоты. Например. :

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

Затем мы сворачиваем вектор и оцениваем:

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

Вот полный код с использованием R и пакета RcppAlgos (я являюсь автором), который написан на 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
    })
}

А вот демонстрация:

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"

Наконец, поскольку нет ограничений на то, какие операции можно использовать, мы нужно подумать о других возможных способах достижения нашей целевой ценности. Приведенное выше решение легко распространяется на более общие случаи. Допустим, мы хотим добавить к смеси умножение. Без проблем:

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"

Я знаю, что кода не было в php, но, надеюсь, идеи, представленные здесь, помогут вам понять, как решить вашу проблему.