方法来递归计算PHP数组中的值？

Question

这个问题在某种程度上与层次数据有关，但我已经从数据库中获得了一个存储过程，该存储过程正在返回下面提到的数据。我不是想了解如何构建层次结构(已完成)，而是试图用PHP (也许是递归数组？)来根据该层次结构计算数字的最佳方法。

使用自定义存储过程，我可以为我们公司的销售代表、他们销售的产品以及新行中的每一种产品及其随后的销售代表(如果在树中)“赚取”百分比。

返回的数据示例如下：

Repnum | Name | productID | sales | earn | depth | parentRep
------------------------------------------------------------
1      |   A  |   1       | 5000  | 0.50 |  1    | 0
1      |   A  |   2       | 10000 | 0.35 |  1    | 0  
2      |   B  |   1       | 400   | 0.40 |  2    | 1
2      |   B  |   2       | 1000  | 0.30 |  2    | 1
7      |   E  |   1       | 30000 | 0.35 |  3    | 2
3      |   C  |   1       | 5000  | 0.33 |  2    | 1

可以安全地假设，返回的数据的顺序已经根据此处未显示的深度和信息进行了适当的格式化和排序。在树视图中，上面的数据如下所示：

1-A-1-5000-0.50-1-0
1-A-2-10000-0.35-1-0
   2-B-1-400-0.40-2-1
   2-B-2-1000-0.30-2-1
      7-E-1-30000-0.35-3-2
   3-C-1-5000-0.33-2-1

在我的while(结果)循环中，我试图为返回的每个repnum计算以下内容：

• 该销售代表的销售总额乘以每个产品的收入%(销售总额和收入总额)。
• 每个下行线树的总销售额乘以当前代表与低于它的级别之间的差额。

为了说明这将是如何工作的数学：

Rep 1收入：

Rep 1 total sales = 5000 + 10000 = 15,000
Rep 1 earn on self = (5000 * 0.50) + (10000 * 0.35) = 6,000 hello!

Rep 2 total sales = 400 + 1000 = 1400
Rep 1 earn on rep 2 sales = (400 * (0.50-0.40) + (1000 * (.35-0.30)) = 90

Rep 7 total sales = 30000
Rep 1 earn on rep 7 sales = (30000 * (0.50-0.40)) = 3000*
(* the reason the earn is calculated at rep 1 earn - rep 2 earn is because in any tree, the "parent" can only ever earn the difference of his/her earn and the direct depth below him/her)

Rep 3 total sales = 5000
Rep 1 earn on rep 3 sales = (5000 * (0.50-0.33)) = 850

**Rep 1 TOTAL earn = 6,000 + 90 + 3000 + 850 = 9,940**

Rep 2收入：

Rep 2 total sales = 400 + 1000 = 1400
Rep 2 total earn on self = (400 * 0.40) + (1000 * 0.30) = 460

Rep 7 total sales = 30000
Rep 2 total earn on rep 7 sales = (30000 * (0.40-0.35)) = 1500*
(* here, rep 2 earns the difference between him/her and rep 7 because he is in the depth right above it / his/her parent)

**Rep 2 TOTAL earn = 460 + 1500 = 1,960**

..。诸若此类

我本可以构建脚本来使用大量mysql递归，只需对每个深度执行大量while()循环，但考虑到我所使用的存储过程并预先计算层次和深度，并对数据进行适当排序，我发现这是不必要的，并且对系统造成了负担。计算最高级别的代表是很简单的，但从名单上的第二个人(以此类推)返回，然后重新开始是我正在挣扎的一些地方。

我希望能够根据上面的示例数据返回类似于以下内容的输出：

num | Name | earnAmount
------------------------
1   |  A   | 9940
2   |  B   | 1960
7   |  E   | 10500
3   |  C   | 1650

提前感谢您的帮助！

关于已提出的问题的说明：

问:收入百分比是如何计算的？ 答:它们不是计算出来的，而是由代表销售的特定productID决定的。

问:你是如何确定“等级”或父母/子女关系的？ 答:我不在这个例子里。这个等式的这一部分是通过一个MySQL存储过程处理的，并且在很多方面都不相关(我也可以为每个rep显示父repnum，但是由于数组是自上而下构建的，所以可能没有太大帮助)。第一个表中示例数据的深度和排序顺序已经被格式化和布局，这样每一棵树都可以通过PHP中的简单print(results_array)语句来打印。

问:在第一个表中，productID的相关性是什么？ 答:每个代表都可以销售我们系统中的任何产品(数百种)，按productID分类。每个销售代表也会为该特定产品赚取一定比例的销售收入。收益率%与特定的产品类型(虽然每个产品都有最大和最小的收入)或特定的深度(虽然在更高的深度上的代表从来没有有一个特定的productID比他的下行树的收入%)完全无关。

问:您的数据在第一个表中是如何排序的？ 答:有点不相干(请相信我)，但在幕后，我创建了一个面包屑列，它接受当前的爬行，然后根据它的组合和树的深度添加子元素和排序。给出的例子：

0 (invisible parent which selects ALL sales reps)
  0-1
    0-1-2
      0-1-2-7
    0-1-3
...

Answer 1

这是我的方法。

我以为数组可以是一维的。depth就足以让我们确定Rep是否有“子”。这个数组看起来是这样的：

$reps = array(
    array("rep" => "1", "name" => "A", "productId" => "1", "sales" => 5000, "earn" => 0.50, "depth" => "1"),
    array("rep" => "1", "name" => "A", "productId" => "2", "sales" => 10000, "earn" => 0.35, "depth" => "1"),
    array("rep" => "2", "name" => "B", "productId" => "1", "sales" => 400, "earn" => 0.40, "depth" => "2"),
    array("rep" => "2", "name" => "B", "productId" => "2", "sales" => 1000, "earn" => 0.30, "depth" => "2"),
    array("rep" => "7", "name" => "E", "productId" => "1", "sales" => 30000, "earn" => 0.35, "depth" => "3"),
    array("rep" => "3", "name" => "C", "productId" => "1", "sales" => 5000, "earn" => 0.33, "depth" => "2")
);

我决定采用递归方法。我们循环遍历earn()函数中的数组，在每次迭代后推进数组指针。在函数中，我们再次在for循环中迭代，从current + 1数组元素开始到结束，以找到Rep的“子”。代码看起来如下：

function earn() {
    global $reps, $earns;
    $rep = current($reps);
    $key = key($reps);
    $immediateChildEarn = null;

    //basic Rep's earnings
    $earn = $rep['sales'] * $rep['earn'];

    //loop to find children with the same productId
    for ($i = $key + 1; $i < count($reps); $i++) {
        $child = $reps[$i];

        //we're only interested in Reps with the same product and deeper position
        if ($rep['productId'] !== $child['productId'] || $rep['depth'] >= $child['depth']) {
            continue;
        }

        //collect the earn of the immediate child
        if (null === $immediateChildEarn) {
            $immediateChildEarn = $child['earn'];
        }

        //the earn difference can't be greater than the difference between Rep and its first immediate child Rep
        if ($immediateChildEarn > $child['earn'] && $rep['depth'] + 1 < $child['depth']) {
            $child['earn'] = $immediateChildEarn;
        }

        //calculate the earnings gained from this child
        $earn += $child['sales'] * ($rep['earn'] - $child['earn']);
    }

    //just a quick fix to prevent throwing Notices - not significant for the algorithm itself
    if (!isset($earns[$rep['rep']])) {
        $earns[$rep['rep']] = 0;
    }

    $earns[$rep['rep']] += $earn;

    $finish = next($reps);
    if (false !== $finish) {
        earn();
    }
}

$earns = array();
reset($reps);
earn();

var_dump($earns)的结果将是：

Array
(
    [1] => 9940
    [2] => 1960
    [7] => 10500
    [3] => 1650
)

请随便评论我的回答。我将尽力修复任何错误，并尽我所能改进代码。

复杂性

我不擅长计算算法的复杂性，但在我的解决方案中，复杂性应该是：

1. 时间复杂度
   • 最坏情况O(n logn)
   • 最佳情形O(2n)

​

1. 内存复杂度(不包括输入数组)
   • 最坏情况O(n)
   • 最佳情况O(1)

​

如果我错了，请随时纠正我。