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}}
[download]

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
[download]

This way, you can get complexity O(m * n) where m is the number of tuples and n is the size of the tuples.