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
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…