# Combinations of mutually disjoint sets

## 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 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 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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
627734
• Total Posts
2978846

• 10
• 10
• 21
• 14
• 12