PHP基于元素依赖关系的排序阵列

Question

解释起来相当困难，但实际上我有一个包含ID的项目数组，其中可以包含其他数组项目的ID列表。例如

$items = [ 
    [id: 'one', deps: ['three']], 
    [id: 'two'], 
    [id: 'three', deps: ['four', 'two']], 
    [id: 'four'] 
]; 

所以，你可以在这里看到，一个取决于三个，三个取决于四个和两个。

我需要获取一个新的数组，它包含这些项目的顺序 - 以便依赖项按顺序列出。因此，上述阵列将转换成

$items = [ 
    [id: 'four'], 
    [id: 'two'], 
    [id: 'three', deps: ['four', 'two']], 
    [id: 'one', deps: ['three']] 
]; 

我该如何完成此？我尝试过各种循环检查项目位置，但无法破解它。

感谢

UPDATE有人说其THIS重复的问题，但主要区别在于上面的例子中含有多的依赖 - 而提到线程只能在一个字符串依赖

Answer 1

你可以使用类似这样的函数，迭代直到满足所有依赖关系，或者不再有依赖关系可以解决：

$items = array(array('id' => 'one', 'deps' => array('three')), 
       array('id' => 'two'), 
       array('id' => 'three', 'deps' => array('four', 'two')), 
       array('id' =>'four')); 


$sortedItems = sortDeps($items); 
var_dump($sortedItems); 

function sortDeps($items) { 
    $res = array(); 
    $doneList = array(); 

    // while not all items are resolved: 
    while(count($items) > count($res)) { 
     $doneSomething = false; 

     foreach($items as $itemIndex => $item) { 
      if(isset($doneList[$item['id']])) { 
       // item already in resultset 
       continue; 
      } 
      $resolved = true; 

      if(isset($item['deps'])) { 
       foreach($item['deps'] as $dep) { 
        if(!isset($doneList[$dep])) { 
         // there is a dependency that is not met: 
         $resolved = false; 
         break; 
        } 
       } 
      } 
      if($resolved) { 
       //all dependencies are met: 
       $doneList[$item['id']] = true; 
       $res[] = $item; 
       $doneSomething = true; 
      } 
     } 
     if(!$doneSomething) { 
      echo 'unresolvable dependency'; 
     } 
    } 
    return $res; 
}