Find non-overlapping pairs of elements in a list whose difference is less than some given threshold

Question

I have the following task: Let us have a list (denoted by L, and for simplicity, the elements come from the interval [0,1]). We are given a parameter (denoted by C), and we want to find as many pairs as we cane (without using the same element twice) in our list, whose difference is at most C.

Example: For the input L=[0, 0.2, 0.4, 0.5, 0.6, 1] and C=0.2, my output should be [0, 0.2] and [0.4, 0.5]. If I had C=0.1, the output would be [0.4, 0.5], and with C=0.4, the output would also contain the pair [0.6, 1]. Getting a single solution is enough, as I know that there are more possible partitions. Note: the input list is not necessary sorted, therefore the pairs don't need to be adjacent.

This is the code that I have created. It tries to search all the possible partitions, then filter the good 2-partitions. As far as I know, it gives the correct solution. My only problem is the runtime: if the list is larger than 20 elements, I can't get the output in a normal time.

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller


def filter_partition(partition):
    for elem in partition:
        if len(elem) not in (1, 2):
            return False
    return True

def get_good_partitions(lista, C):
    lista = lista.tolist()
    all_partitions = list(partition(lista))
    two_partitions = [p for p in all_partitions if filter_partition(p)]
    
    max_pairs = 0
    ret = []
    
    for p in two_partitions:
        is_ok = 0
        for elem in p:
            if len(elem) > 1:
                diff = abs(elem[0] - elem[1])
                if diff <= C or math.isclose(diff, C):
                    is_ok += 1
        if is_ok > max_pairs:
            max_pairs = is_ok
            ret = p
    
    return [elem for elem in ret if len(elem) == 2 and math.isclose(abs(elem[0] - elem[1]), C) or abs(elem[0] - elem[1]) <= C]

#test
L = numpy.array([random.uniform(0, 1) for _ in range(8)])
C = 0.1

res = get_good_partitions(L, C)
print(res)

Answer 1

Your code is doing far too much work.

If we sort the list before we start, then we need only compare adjacent elements as candidates. Whenever we find a pair that satisfies our predicate, then add it to the output and skip forward one step (so we don't consider the second value as a candidate).

---

Example with the list of the question and the threshold for adjacent difference set to 0.125 (which is an exact binary fraction, so avoids problems with floating-point rounding on common platforms):

• Sorted list is [0, 0.2, 0.4, 0.5, 0.6, 1]
• Candidate pair [0, 0.2]: 0.2 > 0.125
• Candidate pair [0.2, 0.4]: 0.2 > 0.125
• Candidate pair [0.4, 0.5]: 0.1 ≤ 0.125 ⇒ accept
• ([0.5, 0.6] is not a candidate, because we just accepted a pair)
• Candidate pair [0.6, 1]: 0.4 > 0.125

Result: [0.4, 0.5] only.

---

A second example, with threshold of 10 this time:

• Input: [11, 50, 55, 45, 0, 51, 33, 19]
• Sorted: 0 11 15 19 33 45 50 51 55
• Paired: 0 [11 15] 19 33 [45 50] [51 55]
• Result: [11, 15], [45 50], [51 55]

---

Note that this algorithm doesn't need any special care to return the maximal number of matching pairs - that will naturally happen because we consider them in sorted order.

Answer 2

You need pairs, not partitions. Your current implementation does a lot of unnecessary work. It looks like you are generating all possible partitions of the input collection and then rejecting the ones containing non-pairs. In other words, you are doing a hard thing in order to do an easy thing. Skip all of that. Here are two easy ways to generate pairs. Beyond that, checking whether each pair meets your criteria is straightforward.

# Roll your own: don't do this unless you must.

def pairs(xs):
    n = len(xs)
    for i in range(0, n):
        for j in range(i + 1, n):
            yield (xs[i], xs[j])

# Use the standard library.

from itertools import combinations

def pairs(xs):
    yield from combinations(xs, 2)

Next steps: if checking all pairs is too slow. If you need to be able to process even larger collections, you'll need a different approach, one that doesn't generate all pairs: for example, sort the input collection and then iterate over each value, in the process examining the value's right-side neighbors and advancing to the next value when the difference between the current value and the current neighbor is too large.