# Efficient way of picking a subset that fulfills criteria

• scienalc
In summary, the conversation discusses a set of elements, S, and its subset, P, which must satisfy certain conditions based on functions f and g. The goal is to efficiently find which elements meet the conditions. One approach is to use brute force, but there may be a more efficient method if f and g are monotonic. This involves finding specific values for d1, d2, and d3 and rewriting the selection criteria in terms of these values. A binary search can then be used to find the remaining boundary values.

#### scienalc

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.

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.