Re^2: (non) nested pairs

ikegami,

Below is some "detector" code that works along the lines as I mentioned above. It determines whether or not I should remove a pair. Its crude because I've ripped it from another function I've written that does a little something different, and the data structures may look a little odd because of that. Hmm... now that I test this further I wonder if I actually had the answer all along, I'll try and come up with an example that doesn't work with this code and report back.


sub pseudoKnotPairs {
    my $self = shift;
    my %p = @_;
    my @r;

    print "\n\n";
    
    my $hel;
    my $h = 0;
    my @keys = sort {$a <=> $b} keys %p;

    map { $hel->{$h} = [$_, $p{$_}]; $h++} (@keys);
        
    # set some flags
    my $reset = 0;
     
    foreach my $k (sort {$a <=> $b} keys %{$hel}) {
        print $k, " ", @{$hel->{$k}}[0], " ",  @{$hel->{$k}}[1], ": ";
+    
        my $nested = 1;
        my $cl = @{$hel->{$k}}[1];
            
        for (my $c = $k+1; $c < $#keys + 1; $c++) {    
             print " $cl";  
            if (@{$hel->{$c}}[1] > @{$hel->{$k}}[1]) { 
                if (@{$hel->{$k}}[1] > @{$hel->{$c}}[0] ) { $nested =0
+ }              
                last;
            }
            if ( $cl <  @{$hel->{$c}}[1]) {
                $nested = 0; 
            }
            $cl = @{$hel->{$c}}[1];     
        }

        # some @r value set below to be returned
        if ($nested == 1) {
            print "\tok!"; 
        }
        else {
            print "\tremove me!";
        }
        print "\n";
    }
    print "\n\n";

    return 1;
}

&pseudoKnotPairs(qw/0 9 3 6 4 5 7 10 8 11/);
[download]

cheers,
M

Comment on Re^2: (non) nested pairs Download Code

Replies are listed 'Best First'.
Re^3: (non) nested pairs by xipho (Scribe) on Dec 25, 2005 at 04:58 UTC
To further muddy the water. With other test data I find that the result with the above code is not quite as desired, as I initially expected (thus the plea for help). While it returns a legal result, its far from optimum. For instance: `&pseudoKnotPairs(qw/0 100 1 99 10 88 11 99/);` [download] Will remove the first 3 pairs. All that would be necessary is to remove one of 10/88 or 11/99 and all three remain pairs would pass the mystical "nested" test.	[reply] [d/l]

Replies are listed 'Best First'.

Re^3: (non) nested pairs
by xipho (Scribe) on Dec 25, 2005 at 04:58 UTC

To further muddy the water. With other test data I find that the result with the above code is not quite as desired, as I initially expected (thus the plea for help). While it returns a legal result, its far from optimum. For instance:

 
&pseudoKnotPairs(qw/0 100 1 99 10 88 11 99/);
[download]

Will remove the first 3 pairs. All that would be necessary is to remove one of 10/88 or 11/99 and all three remain pairs would pass the mystical "nested" test.

[reply]
[d/l]