Совет при создании алгоритма, который сортирует страницы с бесконечной дочерней иерархией - PullRequest
Новая
       14

Совет при создании алгоритма, который сортирует страницы с бесконечной дочерней иерархией

0 голосов
/ 04 мая 2011

Мне нужен совет, когда дело доходит до решения алгоритма сортировки.Этот конкретный алгоритм будет иметь ввод списка из 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}
]

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

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

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

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

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

До сих пор я создал алгоритм, который будет способен к 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;
}

Ответы [ 2 ]

1 голос
/ 04 мая 2011

Нет необходимости в рекурсии.Просто простой цикл над объектами.Для каждого объекта, если его 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}
    ]
1 голос
/ 04 мая 2011

Обычно вы делаете это с какой-то структурой словарных данных. По сути, у вас есть такая структура: 

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
...