Sign in to follow this  

Combinations of mutually disjoint sets

This topic is 3845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to break x integers (lets say the first 9 of them) in groups of y (call it 3) mutually disjoint sets (therefore, each set contains x/y integers). For example (1 3 4) (2 7 8) (5 6 9) (1 5 8) (3 7 9) (2 4 6) etc are acceptable, whereas, say (1 5 7) (3 6 9) (4 6 8) is not, because both the second and the third set ('list' in Lisp) contain number 6. How can I generate all such distinct groups, for arbitrary x and y? Is there any technique or software etc available for that, or (better) any Lisp library functions that accepts those integers and yields the desired output? Thank you in advance. Nikolaos sahtaridis@the.forthnet.gr

Share this post


Link to post
Share on other sites
0. If there are y or less elements left, return them as the only set.
1. Choose an arbitrarily element and remove it from the list of elements (if the elements are in a list, the first on the list would be convenient).
2. Generate all combinations of y-1 of the remaining elements. The element in step 1 plus a generated combination is one disjoint set. For each combination:
3. Recursively call function to generate disjoint sets of the elements that were not used in steps 1 and 2.

Share this post


Link to post
Share on other sites
Or... since your problem description seems to suggest you know x and y initially...

(1) Generate the set of all possible permutations of your base number set.
(2) partition each permutation into the y subsets, each containing x/y elements

Share this post


Link to post
Share on other sites

This topic is 3845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this