Learn the order of elements

  • A+
Category:Languages

I want to find an efficient way (in Perl preferably) to learn the fixed order of a family of words by comparing their order in multiple subsets of the group. (They are job parameters. There are about 30 different ones. Different jobs need different combinations of parameters & there are only ever a few parameters in each job)

For example, given:

first second third sixth seventh tenth  first third fourth fifth sixth  third fifth seventh eighth ninth tenth 

It should be able to remember the relative order relationships it sees to work out that the order is:

first second third fourth fifth sixth seventh eighth ninth tenth 

I have generated lists like:

first.second.third.sixth.seventh.tenth first.third.fourth.fifth.sixth third.fifth.seventh.eighth.ninth.tenth 

then sorted uniquely + alphabetically and visually compared them, but I have hundreds of different combinations of the 30ish parameters, so it will be a big job to sort through them all and put them together manually.

I think @daniel-tran has answered the "how" in https://stackoverflow.com/a/48041943/224625 and using that and some hackery like:

$order->{$prev}->{$this} = 1; $order->{$this}->{$prev} = 0; 

I've managed to populate a hash of hashes with a 1 or a 0 for each pair of consecutive parameters to say which comes first, like:

$VAR1 = {     'first' => {         'second' => 1,         'third' => 1,     },     'second' => {         'first' => 0,         'third' => 1,     },     'third' => {         'first' => 0,         'second' => 0,         'fourth' => 1,         'fifth'  => 1,         'sixth'  => 1,     },                 'fourth' => {         'third' => 0,         'fifth' => 1,     },     ... 

but I hit the wall trying to work out what to do in my sort function when it's asked to sort a pair that have never been seen as immediate neighbours, thus don't have a relationship defined.

Is there an easy solution? Am I going about this the right way? Is there a better WTDI in the first place?

Thanks,

John


The question you linked to includes another answer using a graph and topological sort. The Graph module is pretty easy to use:

use warnings; use strict; use Graph;  my $graph = Graph->new(directed => 1); my $prev; while (<DATA>) {     chomp;     $graph->add_edge($prev, $_) if length && length $prev;     $prev = $_; } print $_,"/n" for $graph->topological_sort;  __DATA__ first second third sixth seventh tenth  first third fourth fifth sixth  third fifth seventh eighth ninth tenth 

Output:

first second third fourth fifth sixth seventh eighth ninth tenth 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: