Не могу решить PHP алгоритм с вариациями - PullRequest
Новая
       35

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

0 голосов
/ 29 августа 2018

Мне нужно найти все возможные решения из данной последовательности целых чисел, равной данному числу.

например: 1,2,3,4,5,6,7,8,9, что равно 100 ответ: 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100

Мое решение для другой суммы в примере 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();

Это результат: 

+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

Настоящая проблема здесь в том, что я не могу согласовать все возможные варианты, как в примере в начале. Заранее спасибо.

1 Ответ

0 голосов
/ 29 августа 2018

Редактировать: Кредит @ m69 за значительное упрощение.

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

Сначала нам нужно взглянуть на ваш пример, чтобы понять, как применяются эти концепции. У нас есть последовательность 1, 2, 3, 4, 5, 6, 7, 8, 9 и a решение 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, но, надеюсь, представленные здесь идеи помогут вам понять, как атаковать вашу проблему.

...