Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^4: Reconstructing List Order From Partial Subsets

by jdporter (Paladin)
on Aug 02, 2006 at 14:01 UTC ( [id://565227]=note: print w/replies, xml ) Need Help??


in reply to Re^3: Reconstructing List Order From Partial Subsets
in thread 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
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.

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; }
    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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://565227]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2024-03-28 18:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found