让我们首先列出我看过的和不要找的东西

我不想列出数组中的所有排列 - Get all permutations of a PHP array?

我不想从数组中按顺序查找所有组合 - https://stackoverflow.com/a/38871855/1260548

上面的两个例子让我走到了现在的位置，但我仍然生成了太多的组合。有了 50 个节点，我最终得到了数十亿甚至数万亿的组合，我认为我可以使用树结构进一步减少它。

我正在寻找的是树中所有可能的有序组合，这些组合可以像这样构造为多维数组

[1]
--[2]
--[4]
[8]
--[3]
--[9]
----[5]
[6]
[7]

我要查找的是所有可能的开放节点(甚至叶/端节点都可以开放)。所以这里的一种可能组合是所有数字，如

• 1.2.3.4.5.8.9

这里的节点 1 是 2 和 4 的父节点。8 是 3 和 9 的父节点。9 是 8 的子节点，但是是 5 的父节点。其他可能的组合是。

• 1
• 1.2.4
• 1.6.7.8
• 3.5.8.9
• 3.5.6.7.8.9

如果父节点未打开，则无法打开节点。例如，如果不包括 1，则不能包括 2 和 4。如果不包括 9 则不能包括 5，如果不包括 8 则不能包括 3、9 和 5。

以下是我用来生成要测试的示例节点结构的代码。请注意，此结构是有序的并且具有固定的深度，因为我想提出一个适用于任何顺序和任何深度的函数。

$arr = [];
$result = [];
$xtotal = 0;
$ytotal = 0;
$ztotal = 0;
for ($x=0; $x<2; $x++) {
  $arr[$xtotal] = array();
  $ytotal = $xtotal+1;
  for ($y=0; $y<2; $y++) {
    $arr[$xtotal][$ytotal] = array();
    $ztotal = $ytotal+1;
    for ($z=0; $z<2; $z++) {
      $arr[$xtotal][$ytotal][$ztotal] = array();
      $ztotal++;
    }
    $ytotal = $ztotal+1;
  }
  $xtotal = $ytotal+1;
}
for ($c=0; $c<5; $c++) {
  $arr[$xtotal] = array();
  $xtotal++;
}

所以我想知道如何编写一个函数来列出所有这些可能的组合？

编辑:使用较小的集合我可以列出所有可能的组合。

[1]
--[2]
--[4]
[8]

1
8
1.8
1.2
1.4
1.2.8
1.4.8
1.2.4
1.2.4.8

最佳答案

我想出了一个函数，似乎可以满足您的需求。但是，在存储所有不同的组合时，您很容易开始遇到内存问题。如果您想要 50 个节点，此解决方案可能不适合您，具体取决于内存限制。

我使用了一些不同的节点生成器(虽然我也用你的进行了测试)这让我在创建随机组合时更加灵活:

$arr = [];
$counter = 0;
// you can change the (2,6) to produce different numbers of root nodes
for($i=1;$i<=mt_rand(2,6);$i++){
    $curr = $counter++;
    $arr[$curr] = [];
    // guarantee the first node (0) will have children nodes (easier testing) - random for other nodes
    $child = ($curr == 0) ? true : rand(0,1);
    if($child){
        // you can change the (1,2)
        for($j=1;$j<=mt_rand(1,2);$j++){
            $curr2 = $counter++;
            $arr[$curr][$curr2] = [];
            $child2 = rand(0,1);
            if($child2){
                // you can change the (1,2) here too
                for($k=1;$k<=mt_rand(1,2);$k++){
                    $curr3 = $counter++;
                    $arr[$curr][$curr2][$curr3] = [];
                }
            }
        }
    }
}

现在开始计算:

function treenodes($arr,&$results,$parent=null){
    foreach($arr as $k=>$a){
        // here we copy all our current results - this gives us one with the current node closed (original), and one with it open (clone)
        $clone = [];
        foreach($results as $key=>$result){
            // if this node is allowed in this result (parent is on) - root nodes are always allowed
            if($parent === null || in_array($parent,$result)){
                $clone[] = array_merge($result,array($k));
            }
        }
        $results = array_merge($results,$clone);
        // if this node has children, run this function on them as well
        if(count($a)){
            treenodes($a,$results,$k);
        }
    }
}
// we start with one option of no nodes open
$results = [[]];
treenodes($arr,$results);

// show results - you can order these another way if you'd like before printing
print count($results)."\n";
foreach($results as $result){
    print implode(",",$result)."\n";
}

关于php - 如何列出一棵树的所有部分树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45368891/