Best algorithm to solve this array problem?-CodePudding

If the for the input, I had a list of lists like so

[[2,1], [1,3], [4,5], [6,8], [4,7]]

How could I find a/the largest subset such that there are no duplicate/shared elements at all?

For this example, an answer would be

[2,1], [4,5], [6,8]

[1,3], [6,8], [4,7]

but an invalid answer would be

[2,1],[1,3],[4,5]

since 1 appears twice here.

My current approach is a recursive approach that uses the idea that either I choose the first element or I don't choose the first element while building the subset but this approach seems way too slow.

What I have: Currently it only returns the size of the largest subset rather than the actual subset but it should be easy to get that once the size is working

def disjointSets(allSets):
    maxCount = 0
    used = set()
    def findDisjoint(currCount, arr):
        nonlocal maxCount
        if not arr:
            maxCount = max(maxCount, currCount)
            return
        elif arr[0][0] in used or arr[0][1] in used:
            findDisjoint(currCount, arr[1:])
            return
        else:
            used.add(arr[0][0])
            used.add(arr[0][1])
            findDisjoint(currCount   1, arr[1:])
            used.clear()
            findDisjoint(currCount, arr[1:])
        return
    findDisjoint(0, allSets)
    return maxCount

CodePudding user response：

What you have here is a graph -- numbers are vertices, and pairs of numbers are edges.

Your problem is to find the largest set of independent edges (edges that don't share a vertex).

This is usually called a maximum matching, and that is a well known problem with well known solutions. The Blossom algorithm is the simplest practical way that is guaranteed to find the best answer.

CodePudding user response：

it might be but i'm not sure if it's fast ! Updated !

matris = [[2,1], [1,3], [4,5], [6,8], [4,7]]
print(matris)

def select(item, matris, selected):
    x = item[0]
    y = item[1]

    if x != y:
        selected.append(item)

    i = 0
    while i < len(matris):
        if x in matris[i] or y in matris[i]:
            matris.pop(i)
            i -= 1

        i = 1 
    
    if len(matris) != 0:
        select(matris[0], matris, selected)
    
    return selected


print("=================")
max_count = 0
for i in range(len(matris)//2 1 if len(matris) % 2 == 0 else len(matris)//2):
    selected = select(matris[i], matris.copy(), [])

    if len(selected) >= max_count:
        max_count = len(selected)
        print(selected)
print("=================")
print("Max Length => "   str(max_count))
print("=================")