[Imperatief]Sorteren van lijst aan de hand van hierarchy

[swendude]

Hallo allemaal!

Ik zit met het volgende probleem. Ik heb een array van integer-paren die een hierarchy aangeven. Bijvoorbeeld:
{{3,1},{4,6},{6,1},{9,3}}

Vervolgens wil ik aan de hand van deze array een nieuwe array maken die de volgorde in de lijst aanhoud.
{a,b} betekent dat b achter a moet komen(niet per se direct erachter)

Dus bij de bovenstaande lijst zou het volgende antwoord kloppen:

{9,3,4,6,1}

Iemand enig idee? Stukje Pseudocode etc zou top zijn!

[Daos]

Kan je niet een gerichte graaf/diagram maken en die dan aflopen waarbij je parallelle routes direct na elkaar in de nieuwe lijst zet.

[Feanathiel]

Volgens mij moet je met de term topo/topological sort een eind komen. Pseudo hiervan staat op de wikipagina, en er zijn een aantal oplossingen in specifieke talen te vinden op het net.

[Daos]

Daos schreef op dinsdag 14 mei 2013 @ 18:39:
Kan je niet een gerichte graaf/diagram maken en die dan aflopen waarbij je parallelle routes direct na elkaar in de nieuwe lijst zet.

Dit werkt (al doe ik het aflopen anders; simpeler maar trager). Na een uurtje heb ik 190 regels C# met als resultaat: {4,6,9,3,1}

edit:
Ik doe het zo:

C#:

private static List<Node> WalkDiagram(List<Node> diagram)
{
    List<Node> list = new List<Node>();

    bool processed_something;
    do
    {
        processed_something = false;

        foreach (Node node in diagram)
        {
            // process only unvisited nodes
            if (node.IsVisited())
                continue;

            // check if node is free
            if (node.IsFree())
            {
                // if so, add node to list and mark it visited 
                list.Add(node);
                node.SetVisited();
                processed_something = true;
            }
        }
    } while (processed_something);

    return list;
}

[ Voor 52% gewijzigd door Daos op 16-05-2013 13:14 ]