Efficient way of picking a subset that fulfills criteria

  • #1
scienalc
16
0
Let's say there is a set of n elements, S. P is a subset of S, with m elements, and satisfies some conditions, i.e. c1 < f(P) < c2 and g(P) < c3, where f and g are some functions on the elements of P and c1, c2 and c3 are constants.

For practical purposes, S is represented as a sorted array of n floating point numbers.

The objective is to find which elements satisfy the above conditions.

My current approach is rather brute force, i.e. exhaustively trying out combinations. I'm wondering whether there is some more efficient way.
 
Technology news on Phys.org
  • #2
In the general case of any f and g, no.

But, for example, if f and g are monotonic, then yes.
In that case:
-- find d1, d2, and d3 for f(d1)=c1; f(d2)=c2; and g(d3)=c3.
-- rewrite the selection criteria in terms of d1, d2, and d3: d1<P<d2 or d1>P>d2 and d3>P or d3<P.
-- if possible, combine those ranges. For example if d1<P<d2; P>d3; and d1<d3; then only d3<P<d2 is needed.
-- do a binary search in S for the d1, d2, and d3 values that remain boundary values.
 

Similar threads

Replies
1
Views
1K
3
Replies
80
Views
7K
Replies
23
Views
2K
Replies
4
Views
2K
Replies
1
Views
2K
Replies
8
Views
2K
3
Replies
100
Views
9K
Back
Top