Your skill will accomplishwhat the force of many cannot PerlMonks

### Searching for the remaining smaller values in an array

by neversaint (Deacon)
 on Jun 20, 2012 at 13:19 UTC 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 ...

Create A New User
Node Status?
node history
Node Type: perlquestion [id://977333]
Approved by muba
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (7)
As of 2018-05-26 22:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (194 votes). Check out past polls.

Notices?