Re: 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
[download]

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

Comment on Re: Reconstructing List Order From Partial Subsets Download Code

Replies are listed 'Best First'.
Re^2: Reconstructing List Order From Partial Subsets by jdporter (Chancellor) 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;` [download] 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.	[reply] [d/l]
Re^3: Reconstructing List Order From Partial Subsets by japhy (Canon) on Jul 26, 2006 at 17:14 UTC
`<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	[reply] [d/l] [select]
Re^3: Reconstructing List Order From Partial Subsets by QM (Parson) on Jul 26, 2006 at 18:11 UTC
Excellent. How do you detect indeterminate conditions? -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]
Re^3: Reconstructing List Order From Partial Subsets by QM (Parson) on Aug 01, 2006 at 22:03 UTC
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	[reply]
Re^4: Reconstructing List Order From Partial Subsets by jdporter (Chancellor) on Aug 02, 2006 at 14:01 UTC
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` [download] `Alpha * Beta * Gamma Delta` [download] 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` [download] My code (in previous node) gets completely cornfused: `Alpha * Beta * Foo * Gamma * Delta` [download] We're building the house of the future together.	[reply] [d/l] [select]
Re^5: Reconstructing List Order From Partial Subsets by QM (Parson) on Aug 02, 2006 at 20:37 UTC


There's more than one way to do things
	PerlMonks