Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Reconstructing List Order From Partial Subsets

by jdporter (Chancellor)
on Jul 26, 2006 at 17:00 UTC ( #563838=note: print w/replies, xml ) Need Help??


in reply to Re: Reconstructing List Order From Partial Subsets
in thread Reconstructing List Order From Partial Subsets

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.

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

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

      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.
        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://563838]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (5)
As of 2022-07-07 08:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?