Welcome toVigges Developer Community-Open, Learning,Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
401 views
in Technique[技术] by (71.8m points)

python - Mutually disjoint sets

I thought I found a solution to the k mutually disjoint sets problem, which is NPC. What is the problem with my solution?

Edit

As requested, problem description:

Input: sets A1, ..., An, and a number k.

Question: do there exist k mutually disjoint sets Ai1 , ..., Aik ?

If I am not mistaken, this does not mean that every two groups should be disjoint. right?

Thanks!

def Algo(A, k):
    for j in range(len(A)-1):
        final_set=[]
        B= intersect(A[j], A[j+1])
        if len(B)==0:
            final_set.append(A[j])
            final_set.append(A[j+1])
        else:
            continue
        temp= [ v for v in A[j]]
        A[j].extend(A[j+1])
        if j+2<len(A):
            for i in range(j+2, len(A)):
                if len(intersect(A[j], A[i]))==0:
                    final_set.append(A[i])
                    A[j].extend(A[i])
        A[j]= temp
        if len(final_set)>=k:
            return True
    return False
               
def intersect(A, B):
    res= []
    for a in A:
        if a in B:
            res.append(a)
    return res

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
等待大神答复

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to Vigges Developer Community for programmer and developer-Open, Learning and Share
...