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.