Efficient way of picking a subset that fulfills criteria

  • #1
16
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
.Scott
Homework Helper
2,464
861
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.
 

Related Threads on Efficient way of picking a subset that fulfills criteria

Replies
0
Views
498
  • Last Post
Replies
16
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
443
  • Last Post
Replies
14
Views
2K
Replies
7
Views
3K
Replies
6
Views
1K
Replies
5
Views
797
Top