Here's a shell script for the case where the sets are too big to fit in memory, assuming that you are on a Unix system and it has a sort program that can sort a file that won't fit in memory.
Input: one file per set, with names of the form set.X. Format of the file is one value per line. E.g., the set (1, 2, 3) might be in file set.0 with contents
1
2
3
Output: each run of the script will merge overlapping set.X files, deleting files that are made redundant. It will tell you how many sets were merged.
Run the script repeatedly until it says "merged 0".
#!/bin/bash
for i in set.*
do
sed -e "s/$/ $i/" m.$$
last_val=-1
last_set=
merged=0
while read in
do
set x $in
if [ $2 -eq $last_val ]
then
if [ -f $3 ]
then
cat $last_set $3 | sort -n | uniq > t
mv t $last_set
rm $3
merged=$((merged + 1))
fi
else
last_val=$2
last_set=$3
fi
done
The above does more passes over the complete set of elements than is necessary, in order to minimize memory use. At the cost of a little more memory, it could write the commands done in the while loop (cat|sort|uniq;mv;rm) out to a file, and then edit that file to adjust it to take into account the affect of the rm's, and then do one pass of merging.
That would look something like this. First, you'd run this script once:
#!/bin/bash
for i in set.*; do sed -e "s/$/ $i/" m
last_val=-1
last_set=
line=2
> s
while read in
do
set x $in
if [ $2 -eq $last_val ]
then
#echo "if [ -f $3 ]; then cat $last_set $3 | sort -n | uniq > t; mv t $last_set; rm $3; fi"
echo "cat $last_set $3 | sort -n | uniq > t; mv t $last_set; rm $3"
echo "$line,\$s/$3/$last_set/g" >> s
line=$((line + 1))
else
last_val=$2
last_set=$3
fi
done c
That gives an output command file, c, that looks like this:
cat set.4 set.7 | sort -n | uniq > t; mv t set.4; rm set.7
cat set.0 set.5 | sort -n | uniq > t; mv t set.0; rm set.5
cat set.1 set.5 | sort -n | uniq > t; mv t set.1; rm set.5
cat set.5 set.7 | sort -n | uniq > t; mv t set.5; rm set.7
cat set.2 set.6 | sort -n | uniq > t; mv t set.2; rm set.6
cat set.3 set.6 | sort -n | uniq > t; mv t set.3; rm set.6
Note the problem with this. Line #1 removes set.7 after merging it with set.4. But line #4 refers to set.7. Since 7 was merged into 4, it needs to refer to set.4 at that point, not set.7.
The script that made c also outputs a file, s, with sed commands to do the above fix. For the above example, it looks like this:
2,$s/set.7/set.4/g
3,$s/set.5/set.0/g
4,$s/set.5/set.1/g
5,$s/set.7/set.5/g
6,$s/set.6/set.2/g
7,$s/set.6/set.3/g
There is still a problem, because note that s suffers from the same problem that c does! Line #4 of s also refers to set.7, but at that point it should be set.4.
So, before using s to fix s, we have to use s to fix s: "sed -f s s2", giving this for s2:
2,$s/set.7/set.4/g
3,$s/set.5/set.0/g
4,$s/set.0/set.1/g
5,$s/set.4/set.0/g
6,$s/set.6/set.2/g
7,$s/set.2/set.3/g
In this case, that is sufficient. We could now "sed -f s2 c2" and then "bash c2", and we'd be left with set.1 and set.3, with the other sets properly merged in.
However, in more complicated cases one application of s to itself is not always enough. What we really should do is keep applying it to itself until we hit a fixed point, so "sed -f s2 s3" giving:
2,$s/set.7/set.4/g
3,$s/set.5/set.0/g
4,$s/set.0/set.1/g
5,$s/set.4/set.1/g
6,$s/set.6/set.2/g
7,$s/set.2/set.3/g
and if you them apply s3 to itself, you will see that there is no change, so s3 is our fixed point. We could then "sed -f s3 c3". Turns out that c3 is identical to c2, so we get the same results as earlier.