Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Sets of subsets

by mzedeler (Pilgrim)
on Jul 22, 2009 at 20:59 UTC ( #782440=note: print w/ replies, xml ) Need Help??


in reply to Sets of subsets

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.


Comment on Re: Sets of subsets
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://782440]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2014-08-01 23:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Who would be the most fun to work for?















    Results (52 votes), past polls