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

How to list all partial trees of a tree

1 Answers