http://qs321.pair.com?node_id=358124

Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All:
Keep in mind this is purely for fun...

One of the most difficult things to do well is correctly prioritizing your responsibilities. I find that with more than a handful of items - using high, medium, and low is just not sufficient. I have also used a numerical scheme ( 1..10 ) but then you run into should this be a 6 or a 7?

What usually is pretty easy is to say that one item is more important than another or that foo depends on bar so bar must come first. Provided enough conditions, the list can only meet all of them in one order. I have seen many puzzles that employ this technique. The problem is what happens if there are contradictory conditions or not enough information that several items are ambigous WRT priority?

My challenge is to develop some code that will order the list given the constriction conditions and identify ambigous items and contradictions with the ability to add/modify/delete conditions until the list can only be in 1 order. I do not care about the interface, or if it has one, though it does scream GUI of some sort. Finally, the less complicated the conditions the better. If it is possible to just relate two items on the list with a higher/lower scheme that would be ideal.

Cheers - L~R

Replies are listed 'Best First'.
Re: Priority Sorting Challenge
by Abigail-II (Bishop) on Jun 01, 2004 at 15:37 UTC
    This is a well know problem in the literature. It's know as "topological sorting". There is a module called 'Sort::Topological' on CPAN, which should do what you want.

    Abigail

[reply]
Re: Priority Sorting Challenge
by Zaxo (Archbishop) on Jun 01, 2004 at 16:23 UTC

    Rather than solving the problem of circular dependencies, Sort::Topological just insists you not have any. Take a look at the Graph module, which has a toposort function. That still doesn't solve detection, but it doesn't blow up: 

    $ perl -MGraph -e'my $g=Graph->new();$g->add_cycle(qw/foo bar baz/);$g
+->add_edge(qw/quux foo/);print $g->toposort()'
quuxbarbazfoo$

    [download]
    You could detect cycles by, for each node, checking if there is a path to any of its predecessors. That will not scale well, but it can be done

    Graph nodes can carry weights, which will allow the priority part of your problem. Properly set up, a minimum spanning tree, $G->MST_Kruskal, should give a solution.

    After Compline,
    Zaxo

[reply]
[d/l]
Re: Priority Sorting Challenge
by davis (Vicar) on Jun 01, 2004 at 15:37 UTC
[reply]
Re: Priority Sorting Challenge
by kvale (Monsignor) on Jun 01, 2004 at 16:00 UTC
    As Abigail-II says, a topological sort is the right algorithm to use if all you have are a set of dependencies to satisfy. If you also have some sort of importance metric on top of the dependencies, the problem is a little harder.

    The topological sort will produce a forest, i.e. a set of dependency trees. Among those trees you will find one containing your most important task. Follow the tree back to the root and execute those tasks needed for the most important task. Mark all these tasks as 'done' and find the next most inportant undone task and repeat the procedue, etc. If there are equal priorities, just pick one randomly or create another criterion that breaks the symmetry.

    For a circular dependency, there is not much to be done, except to restructure your tasks. It is a pathological case and there is no valid solution as far as the computer is concerned.

    -Mark

[reply]
Re: Priority Sorting Challenge
by tachyon (Chancellor) on Jun 01, 2004 at 15:59 UTC 
    #!/usr/bin/perl

END{ print ", finished looking busy!\n" }

use constant HIGH    => 0;
use constant MED     => 1;
use constant LOW     => 2;
use constant URGENCY => 1;
use constant TEMPERO_SPACIAL_RELATIVITY => 2;
use constant NULL    => '';

my @priorities = (
    [ 'a', LOW,  time()+11],
    [ 'b', LOW,  time()+10],
    [ 'c', MED,  time()+9 ],
    [ 'd', MED,  time()+8 ],
    [ 'e', MED,  time()+7 ],
    [ 'f', MED,  time()+6 ],
    [ 'g', MED,  time()+5 ],
    [ 'h', HIGH, time()+4 ],
    [ 'p', HIGH, time()+3 ],
    [ 'a', HIGH, time()+2 ],
    [ 'j', HIGH, time()+1 ],
);

do{ 

  print STDOUT task($_)

} for sort
    { $a->[URGENCY] <=> $b->[URGENCY]
      ||
      $a->[TEMPERO_SPACIAL_RELATIVITY] <=> $b->[TEMPERO_SPACIAL_RELATI
+VITY]
    } @priorities;

sub task {
    my $priority = pop; # goes the weasel
    $priority->[URGENCY] == LOW && do{ sleep LOW, goto SLEEP_MORE };
    $priority->[URGENCY] == MED && do{ sleep MED, goto SLEEP_MORE };
  return $priority->[HIGH];
    SLEEP_MORE:
  NULL
}

    [download]

    cheers

    tachyon

[reply]
[d/l]
Re: Priority Sorting Challenge
by BrowserUk (Patriarch) on Jun 01, 2004 at 15:56 UTC
[reply]

Back to Seekers of Perl Wisdom