Considering elements together which are approximately equal

Question

We have some elements characterized by some key value.

We consider the elements in descending order of key values. So, if we have ten elements with key values, 4, 5, 7, 10, 2, 8, 9, 10, 8.5, 9, we sort the elements by their key values, and consider the elements with equal key values together.

As such, elements with equal key values, e.g. 10, will be considered together, followed by elements with key values 9, and so on. When an element is considered, and it passes a certain fitness function, it is removed from the list and is not considered any more.

Now we relax the restriction of having equal key values to be considered together a little, and consider the elements with approximately equal key values together. So, when we say that in a sorted order the second element is within 10% of the first one, they are to be considered together.

So, now elements with key values 10, 10, 9, 9 are to be considered together. And provided, one element with key value 9 is not removed here, it will have to be considered again with 8.5.

The only way I can think of implementing the above scenario is something like this,

1. Sort the elements in descending order of key values.
2. For the first element in the order, find 10% as allowable deviation. Find elements which fall within this deviation window. So, here we consider, 10, 10, 9, 9, in this window.
3. If any of the elements passes the fitness function, remove it from the list.
4. Form the next window and repeat the cycle.

This is where my idea gets boggled. How do I form the start form the start of next window? If the sorted values are 10, 10, 9, 9, 8.5, 8 ..., and 10, 10, 9, 9, have been considered in the first window, the next window should start with 9 and consist of 9, 8,5.

Is it always sufficient to start the next window the last value of previous window? I tried some counterexamples and none of them invalidated my conjecture. But what if both the 9's pass the fitness function and get removed from the list, which value start the next window? The next one available in the sorted list?

So, my questions are,

1. Is the conjecture regarding starting the next window with the last value (and next one available in the if it gets removed) of previous window correct?
2. Is there a better algorithm for the whole process?

Answer 1

No, it's probably less-than-correct to start the window, from the last value of the previous window.

Try starting from the last window's midpoint initially; then dynamically lower the upper edge, as you iterate the lower edge down, to maintain an appropriate 'span' for the window.

---

It's unclear whether the fitness function & "removal from the list" you describe constitute acceptance of ideal elements, or rejection, or what.

The ideal correct semantics for your windowing, may depend on an accurate specification/ understanding of what that overall operation is -- and your question was sorely lacking in that.