5
\$\begingroup\$

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ It's not clear why the the output would be empty with C=0.1, since 0.6 - 0.5 == 0.1 (0.5 - 0.4 might also be, but that's not guaranteed in the usual IEEE-754 floating-point). Also, is the input list expected to be sorted? Do the pairs have to be adjacent elements, or can they be non-adjacent? \$\endgroup\$ Apr 19, 2022 at 13:06
  • \$\begingroup\$ You are right, with C=0.1, the output should be (0.4, 0.5), or (0.5, 0.6) I will correct that. The input is usually not sorted, and the pairs don't necessary have to be adjacent. \$\endgroup\$
    – Atvin
    Apr 19, 2022 at 13:09
  • \$\begingroup\$ Thanks for the clarifications - your edits improve your question and should help you get better answers. :) \$\endgroup\$ Apr 19, 2022 at 15:52

2 Answers 2

6
\$\begingroup\$

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.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Thanks, this approach helped me understand what I was doing wrong. \$\endgroup\$
    – Atvin
    Apr 19, 2022 at 17:14
  • \$\begingroup\$ FMc's answer also mentions this approach (in the final sentence), but it's possibly a bit terse. FWIW, I wrote this before I noticed it mentioned there. \$\endgroup\$ Apr 19, 2022 at 22:21
  • \$\begingroup\$ The pairs don't have to be adjacent. In [0, 0.05, 0.10, 0.30] [0, 0.10] should be in the solution. \$\endgroup\$
    – Barmar
    Apr 20, 2022 at 14:36
  • \$\begingroup\$ Not necessarily, @Barmar - the solution containing [0, 0.05] is equally acceptable, according to the description. (Perhaps you were misled by the title that all matching pairs need to be returned - but the pair elements need to be distinct. Perhaps we could help rewrite that more clearly?) \$\endgroup\$ Apr 20, 2022 at 15:41
  • \$\begingroup\$ That clause without using the same element twice misled me at first: I thought it meant that each pair needed two distinct values. But following the worked example shows that each value may be used in at most one pair of the entire result. \$\endgroup\$ Apr 20, 2022 at 15:43
6
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.