Re^4: Reconstructing List Order From Partial Subsets

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.

Comment on Re^4: Reconstructing List Order From Partial Subsets Select or Download Code

Replies are listed 'Best First'.
Re^5: Reconstructing List Order From Partial Subsets by QM (Parson) on Aug 02, 2006 at 20:37 UTC
OK. I tried a few variations, and decided to add some randomization. I also changed the `%order` key scheme, though probably for the worse: `my %values; my %order; my %new_order; for (1..10) { my @l = get_values(20); print ">@l\n"; @values{@l} = (); for my $i ( 1 .. $#l ) { for my $j ( 0 .. $i-1 ) { $order{$l[$j]}{$l[$i]} = -1; $order{$l[$i]}{$l[$j]} = 1; } } } my @ordered = sort { $order{$a}{$b} or 0 } keys %values; print ">>@ordered\n"; exit; ############# sub get_values { my $k = shift; my @list; for my $i (1..$k) { push @list, $i if (rand > 0.6); } return @list; }` [download] At 0.6, 10 runs, and a length of 20, I get about 50/50 good/bad results. (You could put together a better test case and plots stats for various values of the 3 inputs.) My data has a very long sequence, hundreds of runs, and a very low threshold. If something is ambiguous, I have to pick a likely sequence anyway. (In some instances there is no single correct sequence, but several that vary in one or two positions...almost like DNA, but that's not what I'm working with.) -QM -- Quantum Mechanics: The dreams stuff is made of	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^5: Reconstructing List Order From Partial Subsets
by QM (Parson) on Aug 02, 2006 at 20:37 UTC

%order

my %values;
my %order;
my %new_order;
for (1..10) {
  my @l = get_values(20);
  print ">@l\n";
  @values{@l} = ();
  for my $i ( 1 .. $#l ) {
    for my $j ( 0 .. $i-1 ) {
      $order{$l[$j]}{$l[$i]} = -1;
      $order{$l[$i]}{$l[$j]} = 1;
    }
  }
}

my @ordered = sort { $order{$a}{$b} or 0 } keys %values;

print ">>@ordered\n";

exit;

#############

sub get_values
{
  my $k = shift;
  my @list;
  for my $i (1..$k) {
    push @list, $i if (rand > 0.6);
  }
  return @list;
}
[download]

My data has a very long sequence, hundreds of runs, and a very low threshold. If something is ambiguous, I have to pick a likely sequence anyway. (In some instances there is no single correct sequence, but several that vary in one or two positions...almost like DNA, but that's not what I'm working with.)

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

[reply]
[d/l]
[select]