不能解决PHP算法的变化

问题描述 投票：7回答：1

我必须从给定的整数序列中找到所有可能的解决方案，它等于给定的数字。

例如：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

这里真正的问题是我不能像开头的例子那样连接所有可能的变化。提前致谢。

php algorithm combinations variations
1个回答
2
投票

编辑：归功于@ m69进行大规模简化。

您的问题可能受到来自Stars and bars的概念的攻击。

我们首先需要查看您的示例，以了解这些概念是如何应用的。我们有序列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++中生成具有重复的排列的算法的快速演示。它很简单，应该很容易转换（here是一个工作的例子）：

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，但希望这里提出的想法将帮助您了解如何攻击您的问题。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.