如何通过多维数组获得所有路径

Question

我问了一个类似的问题，我们没有得到答案（here）。这是我希望的一个更简单的问题。

我想在这里找到每组唯一值。它看起来像一个数组变平，但我如何保持父信息。对于这种树中的答案将是

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' ], 
           ], 
          ], 
         ], 
        ], 
       ], 
      ], 
     ], 
    ]; 

Answer 1

就我个人而言，我会将这个源结构展平为array('45'=>array('3'=>...),...);之类的东西，让生活变得更轻松，但是对于我们自己而言。

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); 

输出：

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

Answer 2

这是一个稍微不同的实现，每次迭代只返回其子路径和不修改调用者的数据。

该函数深入探索树，通过枚举生成所有可能的路径。在每个返回，当前节点被预置到其子的路径，所以

9 => (5, 7 => 3) 

接收（（5），（7,3）），并将其扩展到（（9,5），（9， 7,3）），以及向后传递这给调用者：

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

我只用附带的树测试，你可能要检查对病理情况下：

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 
)