根据父/子关系对数组值进行排序 [英] Sort array values based on parent/child relationship

问题描述

我正在尝试对数组进行排序，以确保任何项的父项始终在数组中之前存在.例如:

I am trying to sort an array to ensure that the parent of any item always exists before it in the array. For example:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [2] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )

    [3] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )

    [4] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [5] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

在上面的数组中，此失败"为[1] [2](Sam)尚不存在，[4] [2](Tom)也不存在.

In the above array this "fails" as [1][2] (Sam) does not yet exist and nor does [4][2] (Tom).

在这种情况下，正确的输出应为Sam和Tom的父母在出现在数组中之前就已经存在:

The correct output would be as, in this case, as both Sam and Tom's parents already exist before they appear in the array:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )


    [2] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [3] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )


    [4] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )


    [5] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

我找到了一个答案 https://stackoverflow.com/a/12961400/1278201 非常接近，但它似乎只深入了一层(即只有一个父级)，而在我的情况下，层次结构中可能只有1层或10层.

I found an answer https://stackoverflow.com/a/12961400/1278201 which was very close but it only seems to go one level deep (i.e. there is only ever one parent) whereas in my case there could be 1 or 10 levels deep in the hierarchy.

如何对数组进行排序，以便除非其父级已经存在，否则无法显示任何值?

How do I sort the array so no value can appear unless its parent already exists before it?

推荐答案

这将琐碎地对数组进行排序(在O(n)中)，将所有没有父对象的对象放在第一位，然后将其父对象已经在数组中的对象依次迭代，直到没有孩子将当前元素作为父元素.

This will trivially order the array (in O(n)) putting first all those with no parent, then these whose parent is already in the array, iteratively, until there's no children having the current element as parent.

# map the children by parent
$parents = ['' => []];
foreach ($array as $val) {
    $parents[$val[2]][] = $val;
}
# start with those with no parent
$sorted = $parents[''];
# add the children the current nodes are parent of until the array is empty
foreach ($sorted as &$val) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

此代码需要PHP 7，在PHP 5下某些情况下可能无法正常工作.-为了与PHP 5兼容，您必须将foreach ($sorted as &$val)与for ($val = reset($sorted); $val; $val = next($sorted))交换:

This code requires PHP 7, it may not work in some cases under PHP 5. - for PHP 5 compatibility you will have to swap the foreach ($sorted as &$val) with for ($val = reset($sorted); $val; $val = next($sorted)):

# a bit slower loop which works in all versions
for ($val = reset($sorted); $val; $val = next($sorted)) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

实时演示: https://3v4l.org/Uk6Gs

这篇关于根据父/子关系对数组值进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！