Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Searching for the remaining smaller values in an array

by neversaint (Deacon)
on Jun 20, 2012 at 13:19 UTC ( #977333=perlquestion: print w/ replies, xml ) Need Help??
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);
and input pair
my @pair = (1,2); my @pair2 = (2,3); my @pair3 = (1,3); my @pair4 = (2,4);
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]
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; }


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

Comment on Searching for the remaining smaller values in an array
Select or Download Code
Re: Searching for the remaining smaller values in an array
by Anonymous Monk on Jun 20, 2012 at 13:23 UTC
Re: Searching for the remaining Smaller values in an array
by Corion (Pope) 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.

Re: Searching for the remaining smaller values in an array
by sundialsvc4 (Monsignor) 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 ...

Re: Searching for the remaining smaller values in an array
by dasgar (Deacon) 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:

    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

    Not saying that this is the "best" way, but it does seem to accomplish what you want.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://977333]
Approved by muba
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (15)
As of 2014-07-14 08:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (257 votes), past polls