It is easier to do as many class divisions as you have positions in each tuple (I guess tuple is a better word in stead of set, since you have the same number of elements in each of them):
Class(a1): {{t1, t2, t3}, {t4}}
Class(a2): {{t1, t3, t4}, {t2}}
Class(a3): {{t1, t4}, {t2, t3}}
While you divide into classes, you'll easilly be able to maintain a distance map like so:
After processing Class(a1):
\ t1  t2  t3  t4
t1 0  0  0  1
t2 0  0  1
t3 0  1
t4 0
After processing Class(a2):
\ t1  t2  t3  t4
t1 0  1  0  1
t2 0  1  2
t3 0  1
t4 0
After processing Class(a3):
\ t1  t2  t3  t4
t1 0  2  1  1
t2 0  1  3
t3 0  2
t4 0
This way, you can get complexity O(m * n) where m is the number of tuples and n is the size of the tuples.
