基于元素依赖的 PHP Order 数组

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

我将如何完成这个？我尝试了各种 while 循环检查项目位置，但无法破解。

谢谢

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

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