looking for a set union find algorithm
Posted
by Mig
on Stack Overflow
See other posts from Stack Overflow
or by Mig
Published on 2010-06-18T06:05:33Z
Indexed on
2010/06/18
6:13 UTC
Read the original article
Hit count: 270
I have thousands of lines of 1 to 100 numbers, every line define a group of numbers and a relationship among them. I need to get the sets of related numbers.
Little Example: If I have this 7 lines of data
T1 T2
T3
T4
T5
T6 T1
T5 T4
T3 T4
I need a not so slow algorith to know that the sets here are:
T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5)
T3 T4 T5 (because T5 is with T4 in line 6 and T3 is with T4 in line 7)
but when you have very big sets is painfully slow to do a search of a T(x) in every big set, and do unions of sets... etc.
Do you have a hint to do this in a not so brute force manner?
I'm trying to do this in python.
Thanks
© Stack Overflow or respective owner