Searching for the remaining smaller values in an array

neversaint has asked for the wisdom of the Perl Monks concerning the following question:

Dear Masters,
Given the following array:

    my @source = (1, 2, 3,  4);
[download]

and input pair

       my @pair  = (1,2);   
       my @pair2 = (2,3);  
       my @pair3 = (1,3);
       my @pair4 = (2,4);
[download]

We would like to find keys in `@source` where the values is smaller than members of any given pairs. So the desired output for each of above pairs are:

    @pair -> []
    @pair2 -> [1]
    @pair3 -> [2]
    @pair4 -> [1,3]
[download]

What's the right algorithm to do that. The following is my code but fail:

    sub get_output {
         my ($source,$pair) = @_;
    
      my @output = ();
      my %done = ();
      foreach my $pr (@{$pair}){
         foreach my $sc (@{$source}){
                 next if ($pr <= $kn || $done{$sc});
                 push @output,$sc;  
                 $done{$sc} = 1;
          
         }
      }
    
      use Data::Dumper;
      print Dumper \@output;
      return @output;
    }
[download]

---
neversaint and everlastingly indebted.......

Comment on Searching for the remaining smaller values in an array Select or Download Code

Replies are listed 'Best First'.
Re: Searching for the remaining Smaller values in an array by Corion (Patriarch) on Jun 20, 2012 at 13:24 UTC
Maybe you want to rephrase the problem? From your examples, I think an equivalent rule for selecting elements would be all elements that are smaller than the smaller element of the pair, and all elements that are between the small and the large element of the pair. Implementing these two rules as routines using `grep` should be easy. It should also be easy to see that the two calls to `grep` do return disjunct lists.	[reply] [d/l] [select]
Re: Searching for the remaining smaller values in an array by dasgar (Priest) on Jun 20, 2012 at 16:27 UTC
First, I would agree that Corion's post more accurately describes the algorithm for your desired output for the given input examples. Got bored, so I came up with the following code: Read more... (2 kB) which produces the following output: `Input list: 1 2 Result list: Input list: 2 3 Result list: 1 Input list: 1 3 Result list: 2 Input list: 2 4 Result list: 1 3` [download] Not saying that this is the "best" way, but it does seem to accomplish what you want.	[reply] [d/l] [select]
Re: Searching for the remaining smaller values in an array by Anonymous Monk on Jun 20, 2012 at 13:23 UTC
crossposted at http://stackoverflow.com/questions/11117530/finding-remaining-smaller-values-in-a-hash-perl	[reply]
Re: Searching for the remaining smaller values in an array by sundialsvc4 (Abbot) on Jun 20, 2012 at 13:55 UTC
You don’t say how many (millions of?) pairs there are, and any other seriously binding constraints upon the problem. It may well be that a straight-ahead linear search will be more than adequate ...	[reply]

Back to Seekers of Perl Wisdom