php - 计算 php 数组 : How to improve my Algorithm? 内可能的解决方案

Question

序言:

这道题不是学习PHP，也不是我打算在生产环境中使用的代码。我只想看到并学习更好的方法来完成这项工作，就像我在我的方法中所做的那样。因此，请仅更正我的代码或向我展示更好、更快或更短的解决方案。问题本身已经解决了。谢谢!

---

问题:

几天前一个用户asked a question在这里。他的问题引起了我的注意，因为我想找到一种方法来解决他的需求。

他想获得 PHP array 的所有可能的键组合，其中值的总和为100，或尽可能接近100。他给了我们一个示例数组，我也将在我的示例中使用它:

$array = array(25, 30, 50, 15, 20, 30);

例如，一个结果应该是[2, 4, 5] ，因为 50 + 20 + 30是100 .

$sum = $array[2] + $array[4] + $array[5]; // = 100

我觉得基本思路应该很清楚了。现在让我们来看看我的工作......

---

我的方法:

所以这个问题引起了我作为开发者的注意。起初，我认为这会很简单。只需做一些加法并检查结果。但后来我注意到有几点需要牢记......

有很多组合可供测试。对于示例数组，将有多达 720 ( 6! = 1*2*3*4*5*6 = 720) 种可能的排列。为了获得所有可能的组合，我想先获得数组的所有可能排列。

但这只是事实的一半。因为数组中可能有 double 值(在您的示例中为 30)，我们无法获得数组值的所有可能排列，我们必须获得数组键的所有可能排列相反。

所以我使用了 pc_permut php cookbook 的功能并根据我的需要修改它。它将返回键数组中所有可能的排列。

/**
 * gets all possible permutations of $array
 * @param array $array
 * @param array $permutations
 * @return array
 */
function permutations($array, $permutations = array()) {
    if( !empty($array) ) {
        $result = array();

        for( $i = count($array) - 1; $i >= 0; --$i ) {
            $newItems = $array;
            $newPerms = $permutations;
            list($values) = array_splice($newItems, $i, 1);
            array_unshift($newPerms, $values);
            $result = array_merge($result, permutations($newItems, $newPerms));
        }
    }
    else {
        $result = array($permutations);
    }

    return $result;
}

此函数的结果是一个多维数组，包含有序键数组中的所有排列。

Array (
    [0] => Array (
        [0] => 0
        [1] => 1
        [2] => 2
        [3] => 3
        [4] => 4
        [5] => 5
    )
    [1] => Array (
        [0] => 1
        [1] => 0
        [2] => 2
        [3] => 3
        [4] => 4
        [5] => 5
    )
    [...
)

所以，现在我可以使用所有排列。可能组合的计算一点也不难。我将循环遍历排列，增加总和直到它们达到 100或以上并返回组合键。

但是我发现我漏掉了一件事。当我得到所有可能的排列时，列表中甚至有一些结果翻了一番。解释一下，这两个结果基本一样:

[2, 4, 5]; // 50 + 20 + 30 = 100
[4, 5, 2]; // 20 + 30 + 50 = 100

我最终在计算后对键进行排序，并将它们用作结果数组中的索引。所以可以肯定的是，每个组合在结果中只存在一次。这是我的combinations功能:

/**
 * gets all possible key combinations of $array with a sum below or equal $maxSum
 * @param array $array
 * @param integer $maxSum
 * @return array
 */
function combinations($array, $maxSum) {
    // get all permutations of the array keys
    $permutations = permutations(array_keys($array));
    $combinations = array();

    // loop all permutations
    foreach( $permutations as $keys ) {
        // create a container for each permutation to store calculation
        $current = array(
            "sum"  => 0,
            "keys" => array()
        );

        // now loop through the permutation keys
        foreach( $keys as $key ) {
            // if the addition is still between or equal $maxSum
            if( $current["sum"] + $array[$key] <= $maxSum ) {
                // increment the sum and add key to result
                $current["sum"] += $array[$key];
                $current["keys"][] = $key;
            }
        }

        // to be sure each combination only exists once in the result
        // order the keys and use them as array index
        sort($current["keys"]);
        $combinations[join("", $current["keys"])] = $current;
    }

    // remove the created key-index from array when finished
    return array_values($combinations);
}

执行简单直接:

$array = array(25, 30, 50, 15, 20, 30);
print_r(combinations($array, 100));

结果是一个数组，包含所有组合。对于我们的示例数组，有十一种可能的组合。结果如下所示:

Array (
    [0] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 1
            [2] => 3
            [3] => 4
        )
    )
    [1] => Array (
        [sum] => 90
        [keys] => Array (
            [0] => 0
            [1] => 2
            [2] => 3
        )
    )
    [...

自从我将此脚本编写为 answer of the original question ，我会问自己，是否有另一种更好的方法来完成这项工作。也许有一种没有排列的方法，或者有一种方法可以从计算或结果数组中排除相同的组合。我知道我可以直接在 permutations 中执行计算功能，但这基本上是相同的工作流程。

我真的很想从你那里得到一些建议、技巧或改进。我认为这里有一些改进脚本的潜力，但实际上我不知道如何改进。但我相信它可以做得更简单直接......

感谢您的宝贵时间! :)

Answer 1

对数组进行排序会导致一些可能性:这是我正在考虑的一种:

我表示 a(selectedIndexes) 由 selectedIndexes 的所有元素组成的元素，例如a({25, 30, 30}) = (25, 30, 30)

P(n) 是索引 1 到 n 的所有组合的集合，为了清楚起见，我的数组从索引 1 开始(因此 P(2)={1, 2, (1, 2)})

我正在使用下面伪代码中解释的 2 个中断条件。第一个是 aSorted 的第一个元素 = 允许的总和。第二个是总和与排序后的第一个元素相比太小

    selectedIndexes = {}
    sum = 100  
    aSorted = {15, 20, 25, 30, 30, 50} //starting values for the example
                                       //to clarify the following function
    aSum = {15, 35, 60, 90}

function n(aSorted, sum, selectedIndexes){
    compute aSum //precisely search in aSum for the index at which
                 //the elements are bigger than sum, and cut
    answer = (P(count(aSum))) X a(selectedIndexes) // with X being the cartesian product

    for (i=count(aSum)+1; i<=count(aSorted); i++){
        newASorted = splice(aSorted, count(aSum))
        // 1st break condition
        if(newASorted is empty) return answer
        // 2nd break condition the new sum < the first element of aSorted
        if (aSorted(i)<sum && sum-aSorted(i)>=aSorted(1)){
            answer += n(newASorted, sum-aSorted(i), push(selectedIndexes,    
            i))
        }
    }
return answer
}

关于数组中元素的数量，这个算法的复杂度感觉是二次方的(快速检查后它更像是 n^log2(n) 阶)

为了让它不那么抽象，让我们开发这个例子(警告我更相信这个例子而不是伪代码，尽管我自己在伪代码中没有看到不准确之处):

n({15, 20, 25, 30, 30, 50}, 100, {}) = P(4) + n({15, 20, 25, 30, 30}, 50, {6}) + n({15, 20, 25, 30}, 70, {5})

从开发等式右边的第一个 n 函数开始

n({15, 20, 25, 30, 30}, 50, {5}) = (P(2) X {6}) + n({15, 20, 25, 30}, 20, { 5, 6}) + n({15, 20, 25}, 20, {4, 6}) + n({15, 20}, 25, {3, 6})

n({15, 20, 25, 30}, 20, {5, 6}) = (P(1) X {(5, 6)})//+ n({15}, 0, { 2, 5, 6}) (but 0<15) 中断条件 2

n({15, 20, 25}, 20, {4, 6}) = P(1) X {(4, 6)}//并打破条件 2

n({15, 20}, 25, {3, 6}) = P(1) X {(3, 6)}//+ n({15}, 5, {2, 3, 6} ) (but 5<15) 打破条件 2

现在开发方程右边的第二个n函数

n({15, 20, 25, 30}, 70, {5}) = (P(3) X {5}) + n({15, 20, 25}, 40, {4, 5} )

n({15, 20, 25}, 40, {4, 5}) = (P(2) X {(4, 5)}) + n({15, 20}, 15, {3, 4, 5})

n({15, 20}, 15, {3, 4, 5}) = P(1) x {(3, 4, 5)}//+ n({}, 0, {1, 3 , 4, 5}) 新的中断条件aSum为空