Re^2: Reconstructing List Order From Partial Subsets

Replies are listed 'Best First'.
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 (Paladin) 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
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]