Maximum number of pairs from list elements satisfying at least a minimum value difference

Given a list l of length n (e.g. n=1000) with (random) integer elements in the range 0<l[i]<10^m (e.g. m=5), what is the maximum number of pairs of two elements one can extract from this list (no element in one pair may overlap with any element in another pair), such that each element pair has at least a minimum difference of their values 0<=diff<10^k with 0<k<=m?

The naïve approach of generating all possible partitions and checking each for the largest number of pairs with sufficient distance in values is very inefficient. How could we do this in a smart way?

EXAMPLE:

Consider list l to be given by:

l = {1, 2, 8, 9, 10, 15};  

and the minimum difference between elements in admissible pairs diff=7. Then we can construct the following sets of disjoint pairs satisfying the element distance requirements:

{ {1,8} , {2,9} }    { {1,8} , {2,10} }    { {1,8} , {2,15} }    { {1,9} , {2,10} , {8,15} }    { {1,9} , {2,15} }    { {1,10} , {2,9} , {8,15} }    ...etc  

Note that all pairs selected have elements such that larger element minus smaller element is bigger or equal to the minimum value diff=7 as required. In the above example, as soon as we encounter a case where the maximum number of pairs (e.g. 3) can be built, we can stop, since we found out that the answer is 3. But it may happen that a list only admits a maximal number of such pairs that is less than half of the length of l. List l also may have multiple elements with the same value, in which case combinations involving one are not equivalent to numerically same combinations involving the other (but presumably their number of pairs will be the same).

https://stackoverflow.com/questions/66492579/maximum-number-of-pairs-from-list-elements-satisfying-at-least-a-minimum-value-d March 05, 2021 at 08:25PM