Блог

Мне нужен совет, когда дело доходит до решения алгоритма сортировки. Этот конкретный алгоритм будет иметь на входе список из n элементов. У каждого элемента есть идентификатор и родительский идентификатор. Вот так:

 [
    {id : 1, parent_id : 0},
    {id : 2, parent_id : 1},
    {id : 3, parent_id : 1},
    {id : 4, parent_id : 2},
    {id : 5, parent_id : 4},
    {id : 6, parent_id : 0}
]
  

Вот ожидаемый результат:

 [
    {id : 1, parent_id : 0, children:
    [
        {id : 2, parent_id : 1, children:
        [
            {id : 4, parent_id : 2, children:
            [
                {id : 5, parent_id : 4}
            ]}
        ]
        },
        {id : 3, parent_id : 1}            
    ]},
    {id : 6, parent_id : 0}
]
  

Моей первоначальной идеей было разбить алгоритм на уровни иерархии, рекурсивно анализируя каждый уровень. Так что теоретически это выглядит примерно так:

• Сравните каждый элемент в несортированном списке со всеми элементами, чтобы увидеть, есть ли совпадения, поместите все совпадения в дочерний узел каждого родительского узла, поместите каждого родителя в переменную отсортированного списка.
• Сравните каждый элемент в дочернем узле со всеми элементами в несортированном списке, чтобы увидеть, есть ли у них совпадения, поместите совпадения в каждом дочернем узле в их собственный дочерний узел.
• Продолжайте последний шаг, пока на каждом уровне не останется совпадений.

Я только начал изучать некоторые парадигмы функционального программирования и начал читать больше об алгоритме и анализе, просто потому, что я не знаком с рекурсивным мышлением.

Итак, мои вопросы:

• Что вы посоветуете при работе с подобной логикой?
• Как мне научиться мыслить правильным образом?
• Глядя на мой текущий алгоритм, я чувствую, что понял концепцию, за исключением того, что я действительно не знаю, как заставить вторую проверку работать как рекурсивное решение. Я далек от правильного направления?

На данный момент я создал алгоритм, который будет поддерживать 2 уровня иерархии. Это выглядит примерно так (в настоящее время написано на php и является просто кодом подтверждения концепции):

 function sortParentsChildren($unsortedList, $parentIDKey = "parent_id", $childNameKey = "children"){
    $sortedList = array();

    foreach($unsortedList as $key => $value){
        $children = array();
            //See if there are any children for this item
        foreach($unsortedList as $skey => $svalue){
            if($value["id"] == $svalue[$parentIDKey]){      
                $children[] = $svalue;
            }
        }

            //Add all items with parent id = 0 to the root
        if($value["parent_id"] == 0){
            $sortedList[$key] = $value;
        }   

            //Check if there were any children
        if(sizeof($children) > 0){
                    //Search each children and see if they have any matches
            foreach($children as $ckey => $cvalue){
                foreach($unsortedList as $s2key => $s2value){
                    if($cvalue["id"] == $s2value[$parentIDKey]){        
                        $children[$ckey][$childNameKey][] = $s2value;
                    }
                }                   
            }

            $sortedList[$key] = $value;
            $sortedList[$key][$childNameKey] = $children;
        }
    }

    return $sortedList;
}
  

Обычно вы делаете это с помощью какой-то словарной структуры данных. В принципе, у вас есть структура, подобная этой:

 Node
{
    int id;
    int parent;
    Node[] children;
}
  

Вы сохраняете это в словаре или ассоциативном массиве с ключом id. Создайте узел со значением идентификатора 0 и родительским идентификатором, равным -1.

Отсортируйте свой входной массив по родительскому идентификатору, а затем просмотрите список. Для каждого элемента добавьте его в словарь. Также найдите его родительский узел (который уже есть в словаре, поскольку входной список был отсортирован по родительскому идентификатору) и добавьте новый узел в родительский список дочерних элементов.

Когда вы закончите, узел[0] содержит построенную иерархию.

Я не очень разбираюсь в PHP-программировании, поэтому вам придется обойтись псевдокодом:

 Nodes = new associative array
Nodes[0] = new Node(0, -1)
sortedInput = sort input by parent id
foreach item in sortedInput
    Nodes[item.id] = new Node(item.id, item.parent);
    //Nodes[item.parent].Children.Add(Node);
    // Above line commented and replaced with this.
    Nodes[item.parent].Children.Add(Nodes[item.id]);
end

// Nodes[0] contains the hierarchy
OutputNode(Nodes[0], "")
  

Функция для вывода иерархии является рекурсивной:

 OutputNode(Node, indent)
    print indent, Node.id, Node.parent
    foreach (child in Node.children)
        OutputNode(child, indent "  ");
    end
end
  

Нет необходимости в рекурсии. Просто простой цикл по объектам. Для каждого объекта, если его parent_id равен 0, скопируйте его в массив ответов. В противном случае получите доступ к родительскому объекту по его местоположению в массиве и добавьте текущий объект к его списку дочерних элементов.

Вот как это работает для вашего массива. Внимательно обратите внимание на результат того факта, что при однократном обновлении объекта обновляются все копии этого объекта.

 0: Start
    answer = []
    objects = [
        {id : 1, parent_id : 0},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

1: Append object 1 to answer
    answer = [
        {id : 1, parent_id : 0}
    ]
    objects = [
        {id : 1, parent_id : 0},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

2: Append object 2 to children of object 1
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

3: Append object 3 to children of object 1
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

4: Append object 4 to children of object 2
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3}
            ]}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3}
        ]},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

5: Append object 5 to children of object 4
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3, children : [
                {id : 5, parent_id : 4}
            ]}
        ]},
        {id : 4, parent_id : 3, children : [
            {id : 5, parent_id : 4}
        ]}
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

6: Append object 6 to answer
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 6, parent_id : 0}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3, children : [
                {id : 5, parent_id : 4}
            ]}
        ]},
        {id : 4, parent_id : 3, children : [
            {id : 5, parent_id : 4}
        ]}
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]