Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

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

Replies are listed 'Best First'.
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 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:

    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.

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

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2020-02-18 01:53 GMT
Find Nodes?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?

    Results (74 votes). Check out past polls.