Advertisement

Combinations of mutually disjoint sets

Started by June 08, 2007 06:08 AM
1 comment, last by Timkin 17 years, 8 months ago
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
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.
Advertisement
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

This topic is closed to new replies.

Advertisement