http://qs1969.pair.com?node_id=563832


in reply to Reconstructing List Order From Partial Subsets

Using liverpole's hash idea, I've come up with this (updated with comments):
use strict; use warnings; my (%pos, @order); # collect the position information { local $/ = ""; while (<DATA>) { chomp; my $i = 0; # $pos{TERM}{SET #} = POSITION $pos{$_}{$. - 1} = $i++ for split /\n/; } } # extract order from the positions for my $i (1 .. keys %pos) { # get all terms who appear ONLY in position 0 # across all the sets they're in my ($first, @extra) = grep { my $t = $_; my %p = map { $_ => 1 } values %{ $pos{$t} }; $p{0} and keys(%p) == 1 } keys %pos; # if there was more than one term found, cause a fuss warn "iteration #$i: multiple candidates [$first @extra]\n" if @extr +a; # uncomment for debugging to see how %pos changes # use Data::Dumper; print Dumper(\%pos); # get the sets this term appeared in and alter # the positions of terms found in those sets for my $set (keys %{ delete $pos{$first} }) { $pos{$_}{$set} and $pos{$_}{$set}-- for keys %pos; } # store this term in the ordered list push @order, $first; } print "<@order>\n"; __DATA__ alpha beta epsilon zeta beta gamma zeta alpha gamma delta epsilon

Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart

Replies are listed 'Best First'.
Re^2: Reconstructing List Order From Partial Subsets
by jdporter (Paladin) on Jul 26, 2006 at 17:00 UTC
    my %values; my %order; while (<DATA>) { chomp; my @l = split /\n/; @values{@l} = (); for my $i ( 1 .. $#l ) { for my $j ( 0 .. $i-1 ) { $order{"$l[$j]\t$l[$i]"} = -1; $order{"$l[$i]\t$l[$j]"} = 1; } } } my @ordered = sort { $order{"$a\t$b"} or 0 } keys %values;

    Update: Don't use this. It does not work. It may appear to work for some test cases, but it is fundamentally flawed. Sorry.

    We're building the house of the future together.
      <deniro>You. You! You... you're good.</deniro>

      Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
      How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
      Excellent.

      How do you detect indeterminate conditions?

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

      Update: Don't use this. It does not work. It may appear to work for some test cases, but it is fundamentally flawed. Sorry.
      Do you have an example of a failing test case? It may still be useful for what I had in mind...

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

        Yes. Here is a simple graph with a single ambiguity: it cannot tell whether Beta or Gamma should come first. Note that in the output these are flagged as ambiguous.

        Alpha Beta Alpha Gamma Beta Delta Gamma Delta Alpha Delta
        Alpha * Beta * Gamma Delta

        Now, to try to resolve the Beta/Gamma order, I introduce a simple link through a new node, Foo:

        Alpha Beta Alpha Gamma Beta Delta Gamma Delta Alpha Delta Beta Foo Foo Gamma

        My code (in previous node) gets completely cornfused:

        Alpha * Beta * Foo * Gamma * Delta
        We're building the house of the future together.