How to list all partial trees of a tree

Question

Let's begin by listing what I have looked at and what I am not looking for

I do not want to list all the permutations from an array - Get all permutations of a PHP array?

I do not want to find all combinations in order from an array - https://stackoverflow.com/a/38871855/1260548

The two above examples got me to where I am now but I still generate too many combinations. With 50 nodes I end up with billions if not trillions of combinations and I think I can reduce this further with a tree structure.

What I am looking for is all the possible ordered combinations from a tree which could be structured as a multidimensional array like so

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

What I want to find are all the possible open nodes (even leaves/end nodes can be open). So one possible combination here is all the numbers like

• 1.2.3.4.5.8.9

node 1 here is a parent of 2 and 4. 8 is a parent of 3 and 9. 9 is a child of 8 but a parent of 5. Other possible combinations are.

• 1
• 1.2.4
• 1.6.7.8
• 3.5.8.9
• 3.5.6.7.8.9

It is not possible to open a node if the parent is not open. For example, if 1 is not included then 2 and 4 can not be included. If 9 is not included then 5 can not be included and if 8 is not included then 3, 9 and 5 can not be included.

The following is code I use to generate a sample node structure to test with. Please note that this structure is ordered and has a fixed depth where as I would like to come up with a function that will work with any order and any depth.

$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++;
}

So I am wondering how to go about writing a function that would list all these possible combinations?

EDIT: With a smaller set I can list all possible combinations.

[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

Answer 1

I've come up with a function that seems to do what you are looking for. However, in storing all the different combinations, you can easily start running into memory issues. If you want 50 nodes, this solution might not work for you depending on memory limits.

I used a little bit different node generator (though I did test with yours too) that allowed me more flexibility in creating random combinations:

$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] = [];
                }
            }
        }
    }
}

Now for the calculating:

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";
}