Find longest combination of non-overlapping pairs

user_19736824 0
Viewed 55

I need to find the length of the longest combination of pairs that can be made from a list of pairs, without any common elements.

For example the following list of pairs:

[(A, B), (A, D), (B, C), (B, D), (C, D)]

Would have these combinations:

[(A, B), (C, D)] 
[(A, D), (B, C)]
[(B, D)]

And so the longest combination would be 2 pairs in length.

This needs to be able to handle up to several thousand pairs so generating all possible combinations of pairs at each possible length and checking for overlaps would not work.

However, the total number of unique elements across all pairs is capped at 100, so the longest possible combination that could be encountered would be 50 pairs.

Is there an efficient way to do this?

combinations combinatorics python
2 Answers

okay this is what I have, maybe not the best but its something

so Combo initializes any 2 pairs, and feeds it to Combine along with the rest of the array not check yet

Combine takes an the leftover array, the current combo and a list of used elements, then check each possible combination, if the check tuple from the leftover array has any elements in the used list, it skips it, if it doesnt, it adds it to the combo and passes it to a further recursed Combine until its as long as it can be

arr = [('A', 'B'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('E', 'D'), ("A",'F'),('J','K'),('M','K'),('K','D'),('B','F')]

def Combo(arr):

    combos = []

    for i, tup1 in enumerate(arr):
        combo = [tup1]
        used = [tup1[0], tup1[1]]
        for j, tup2 in enumerate(arr[i:]):
            if (tup2[0] in used) or (tup2[1] in used):
                continue
            else:
                for el in tup2:
                    used.append(el) 
                combo.append(tup2)
                combo=Combine(arr[j:], combo, used)
            combos.append(combo)
    return combos


def Combine(arr, combo, used):
    if arr==[]:
        return combo
    for i, tup in enumerate(arr):
        unique = True
        for el in tup:
            if el in used:
                unique = False
                continue
        if unique:
            combo.append(tup)
            for el in tup:
                used.append(el)
            return Combine(arr[i:], combo, used)
        
    return combo


Combo(arr)

OUTPUT

[[('A', 'B'), ('E', 'D'), ('J', 'K')],
[('A', 'D'), ('B', 'C'), ('J', 'K')],
[('B', 'C'), ('E', 'D'), ('A', 'F'), ('J', 'K')],
[('B', 'D'), ('A', 'F'), ('J', 'K')],
[('E', 'D'), ('A', 'F'), ('B', 'C'), ('J', 'K')],
[('A', 'F'), ('J', 'K'), ('B', 'C'), ('E', 'D')],
[('J', 'K'), ('B', 'F'), ('E', 'D')],
[('M', 'K'), ('B', 'F'), ('E', 'D')],
[('K', 'D'), ('B', 'F')]]

as far as I know this should give you each unique combination in a list

user_187850850

Rephrasing the question, we want to find the biggest set of non-overlapping elements of pairs. Probably not the best solution but should work:

def process(pairs):
    output = {}
    max_length = 0
    for i in range(len(pairs)):
        curr = 1
        output[pairs[i]] = set(pairs[i])
        rest = pairs[:i] + pairs[i + 1:]
        for j in range(len(rest)):
            subset = output[pairs[i]] | set(rest[j])
            if len(subset) == len(output[pairs[i]]) + 2:
                curr += 1
                output[pairs[i]] = subset
            max_length = max(curr, max_length)
    return max_length

We populate our initial set with the current pair and then if the next pair's elements are not presented in the current set we extend it. We continue this process until we checked all remaining pairs. I used this function for testing:

import random, timeit

def get_random_pairs(num):
    return [(random.choice(string.ascii_uppercase), random.choice(string.ascii_uppercase)) for _ in range(num)]

print(timeit.timeit('process(pairs)', number=5, setup="from __main__ import process,get_random_pairs; pairs = get_random_pairs(3000)")/5)

On my machine (Intel i7-9750H (12) @ 4.500GHz) it takes about 5-6 seconds to process 3000 pairs.

user_99267210
Related