Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Sorting, given only comparisions

by Anonymous Monk
on Sep 08, 2001 at 06:50 UTC ( #111117=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi
I have data in comparision forms:
a1 a2 1
a2 a3 1
a4 a5 1
a5 a6 1
a6 a7 1
a1 a5 1
a5 a2 1
a4 a1 1
a7 a8 0
above indicates ex. a2 is larger than a3 and a7 is same as a8.
First 2 lines also implies that a1 is larger than a3

I have to find where there is any comparision can be obtained or derived between given elements. ex. a3 and a6. ie.. whether a3 is larger , smaller or equal to a6 OR no relationship is defined yet between them.

The idea that comes to my mind is to find out all smaller elements than a3 and find out all larger elements and than check both array for a6.

Your suggestions will be helpful.
Thanks,

Comment on Sorting, given only comparisions
Re: Sorting, given only comparisions
by Anonymous Monk on Sep 08, 2001 at 08:40 UTC
    Hi,
    I have a homework assignment. I am posting here because I don't want to do it myself.
    Your suggestions will be helpful.
    Thanks,
      Nope Not a homework,
      and I have the code:
      Just looking for something better..
      my (%big,%small); while(<DATA>){ my ($p1,$p2,$n) = split; push @{$big{$p2}},$p1; push @{$small{$p1}},$p2; } sub Larger{ my ($s1,$s2) = @_; my @strings; my @strings2; my $debug = 0; print " $s1 ? $s2 \n"; my (@big,@small); my %seen; my @elements = ($s1); my $count; my %added; while(my $x = shift @elements){ next if $seen{$x}; $seen{$x}++; foreach (@{$big{$x}}){ next if $seen{$_}; next if $added{$_}; push @big, $_; $added{$_}++; push @elements, $_; } } print "Larger:"; print join " ",@big,"\n"; }
Re: Sorting, given only comparisions
by blakem (Monsignor) on Sep 08, 2001 at 10:38 UTC
    For anyone who read What's the big deal? and was disappointed that Logical Programming took a backseat to the other three branches of programming, this current question is framed in a very Logical Programming kind of way.

    First we list some "Truths" about our world, then we attempt to derive the truthfulness of other relationships, based on the principals of logical reasoning.

    The dearth of answers here shows that perl doesn't intuitively behave this way. For logical programming languages, this problem is trivial (could probably be the first example in the intro book), because they are designed to solve exactly this type of problem.

    Sorry I didn't address the actual question.... perhaps someting like Prolog is better suited for this. (Though I'm sure some clever person will work some sort of perl solution out...)

    -Blake

      Hi Blakem,
      Appreciate your thoughts and agree with your perception:

      Not to disappoint you, but I haven't considered prolog for this task, as the entire system is written in perl.
      What this means that it gives us an opportunity to mimic prolog/logical programming via perl modules and operator overloading.

      First we list some "Truths" about our world, then we attempt to derive the truthfulness of other relationships, based on the principals of logical reasoning.
      I defintely liked your verbal derivation of the problem. What I have mentioned is just a simple ranking problem. Your idea could be applied in general and we can prepare a complex data set to come up with the complicated query.
      More pointers in this direction, if you have done some research, would be definitely helpful.

        While I haven't tried it myself, princepawn has a module by the name of AI::Proplog that might be what you're looking for. My reading of the POD is that it's still somewhat preliminary, but it seems to be a start in the direction you're looking.



        If God had meant us to fly, he would *never* have given us the railroads.
            --Michael Flanders

Re: Sorting, given only comparisions
by Zaxo (Archbishop) on Sep 08, 2001 at 11:28 UTC

    This is mostly a topological sort. If you substitute a7 for a8 it is entirely a topological sort. The question becomes whether cycles exist to refute the ordering.

    System tsort will handle this. So will the Graph module. Wolf Book pp304-307 does, too.

    After Compline,
    Zaxo

Re: Sorting, given only comparisions
by ariels (Curate) on Sep 09, 2001 at 10:27 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://111117]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (9)
As of 2014-11-27 18:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (187 votes), past polls