How to get all paths through a multidimensional array

Question

I asked a similair questions and we didn't get to an answer (here). This is a simpler question I hope.

I want to find each set of unique values here. It seems like a array flatten, but how do i keep the parent information. For this tree the answers would be

45, 3, 88
45, 2, 77
45, 5, 67, 2, 35
45, 5, 67, 3, 44

$tree = [ 
    0 => '45', 
    1 => [ 
        0 => [ 
            0 => '3', 
            1 => [ 
                    0 => [0 => '88'],
                ], 
            ], 
        1 => [ 
            0 => '2', 
            1 => [ 
                    0 => [ 0 => '77'], 
                ], 
            ],
        2 => [ 
            0 => '5', 
            1 => [ 
                0 => [ 
                    0 => '67', 
                    1 => [ 
                        0 => [ 
                            0 => '2', 
                            1 => [ 
                                0 => [ 0 => '35' ], 
                                ], 
                            ], 
                        1 => [ 
                            0 => '3', 
                            1 => [ 
                                0 => [ 0 => '44' ], 
                                ], 
                            ], 
                        ], 
                    ], 
                ], 
            ], 
        ], 
    ];

Can you share what you have tried and tell us where that falls short of achieving your goal? — Jay Blanchard, Sep 05 '14 at 16:42
possible duplicate of [Traverse a tree like array to find maximum span in PHP](http://stackoverflow.com/questions/25650175/traverse-a-tree-like-array-to-find-maximum-span-in-php) — Lkopo, Sep 05 '14 at 17:00

score 3 · Accepted Answer · answered Sep 05 '14 at 18:18

Personally, I'd flatten out that source structure to something like array('45'=>array('3'=>...),...);, to make life easier, but to each their own I suppose.

function traverse($arr, &$return, $path=NULL) {
    // track the current path through the tree
    $path[] = $arr[0];
    if( isset($arr[1]) && is_array($arr[1]) ) {
        // descend through each branch
        foreach($arr[1] as $i) {
            traverse($i,$return,$path);
        }
    } else {
        // store path each time we reach a leaf
        $return[] = $path;
    }
}

traverse($tree, $return);
var_dump($return);

Output:

array(4) {
  [0]=>
  array(3) {
    [0]=>
    string(2) "45"
    [1]=>
    string(1) "3"
    [2]=>
    string(2) "88"
  }
  [1]=>
  array(3) {
    [0]=>
    string(2) "45"
    [1]=>
    string(1) "2"
    [2]=>
    string(2) "77"
  }
  [2]=>
  array(5) {
    [0]=>
    string(2) "45"
    [1]=>
    string(1) "5"
    [2]=>
    string(2) "67"
    [3]=>
    string(1) "2"
    [4]=>
    string(2) "35"
  }
  [3]=>
  array(5) {
    [0]=>
    string(2) "45"
    [1]=>
    string(1) "5"
    [2]=>
    string(2) "67"
    [3]=>
    string(1) "3"
    [4]=>
    string(2) "44"
  }
}

score 0 · Answer 2 · answered Sep 05 '14 at 19:45

This is a slightly different implementation, each iteration only returns its subpaths and does not modify the caller's data.

The function explores the tree in depth, generating all the possible paths by enumeration. At each return, the current node is prepended to the path of its children, so

9 => ( 5, 7 => 3 )

receives ( ( 5 ), ( 7, 3 ) ) and expands it to ( ( 9, 5 ), ( 9, 7, 3 ) ), and passes this backwards to the caller:

function enumerateArray($arr) {
    if (1 == count($arr)) {
        // Leaf: one path only is possible, and it has $arr[0].
        return [ $arr ];
    }
    // This node will prefix all the paths of its children.
    list($node, $children) = $arr;
    $paths  = [ ];
    foreach ($children as $child) {
        // Get all the paths of this child
        foreach(enumerateArray($child) as $subpath) {
            // Add the path, with prefix, to possible paths
            array_unshift($subpath, $node);
            $paths[] = $subpath;
        }
    }
    return $paths;
}

I only tested with the supplied tree, you might want to check against pathological cases:

print_r(
    array_map(
        function($path){
            return implode(', ', $path);
        }, 
        enumerateArray($tree)
    )
);

Array
(
    [0] => 45, 3, 88
    [1] => 45, 2, 77
    [2] => 45, 5, 67, 2, 35
    [3] => 45, 5, 67, 3, 44
)

How to get all paths through a multidimensional array

2 Answers2