doulan4939 2016-09-26 20:21
浏览 45
已采纳

PHP Order数组基于元素依赖

Fairly hard one to explain, but effectively I've got an array of items which have IDs, of which can contain a list of IDs for other array items. for example

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

So as you can see here, one depends on three, and three depends on four and two.

I need to get a new array, that contains these items in order - so that the dependencies are listed in order. So the above array would convert into

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

How would I complete this? I've tried various while loops checking for item positions, but can't crack it.

Thanks

UPDATE Some people have said its a duplicate question of THIS but the main difference being the above example has multiple dependencies - whereas the mentioned thread only works on a single string dependency

  • 写回答

1条回答 默认 最新

  • doukui9491 2016-09-26 22:17
    关注

    you can use a function like this, that iterates until all dependencies are met, or no more dependencies can be resolved:

    $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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 怎么在stm32门禁成品上增加记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 解riccati方程组