Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I can choose 2 letters from the four letters $\{A,B,C,D\}$ in 6 combinations using the combination formula

$$\frac{n!}{ r! (n-r)!}$$

{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}

Consider now the collection of all subsets of a set of $n$ elements and restrict to those having exactly cardinality $k$, such as $k=2$ above. How can I find all combinations of groups of 2 or 3 or ... or $n$ (should be dynamic) of these which do not have letters in common? So, for example, I am expecting the result for combinations of two groups of $k=2$ elements to be the three collections below:

{{A, B}, {C, D}},

{{A, C}, {B, D}},

{{A, D}, {B, C}}

This is just a small example but I would like the algorithm to work for a large number of sets (I have more than 35000 sets).

share|improve this question
    
The number of letters change or you will just use 4? –  Spawn1701D Apr 18 '13 at 18:27
    
Aren't they the permutations, properly splitted? –  belisarius Apr 18 '13 at 18:33
    
@belisarius I don't think so. For example, splitting ABCD into groups of two gives the same partition as splitting BACD, ABDC, BACD, CDAB, etc. –  whuber Apr 18 '13 at 18:49
1  
user, this may be a duplicate of your question, though phrased differently: mathematica.stackexchange.com/q/3044/121 -- please review that, and if it is not, make clear in this question why not. –  Mr.Wizard Apr 19 '13 at 3:22
1  
Yes, it is same, i couldn't find it. But I am not from pure mathematics, I am a programmer so want the programming algorithm to solve this problem. –  user1191081 Apr 19 '13 at 12:55
show 7 more comments

1 Answer 1

up vote 8 down vote accepted

It is desired to find all collections $P = \{A_1, A_2, \ldots, A_m\}$ of $m$ disjoint $k$-subsets of a finite set $X$. Such collections consist of two types: those which include a specified element of $X$ (say $a$) and those that do not. If $a \in A_j$ for some $j$ then we might as well reindex the elements of $P$ so that $j=1$. All possibilities for $A_1$ are found by adjoining all possible $k-1$-element subsets of $X - {a}$ to $a$, whereas all possibilities for the $A_2, \ldots, A_m$ are found recursively for $X - A_1$ with $m=1$. Otherwise, $a$ is not in any $A_j$ and we are left to find similar collections for $X - {a}$.

This gives the following recursive solution. It's not fast but it's not slow, either--see the timing example below.

Please note that the number of solutions grows very, very quickly with $k$ and $m$. Their number is computed with combinationsCount, which uses Multinomial to obtain

$$\frac{n!}{k!^m (n - m k)! m!}.$$

The numerator is the size of the permutation group on $X$ while the denominator is the size of the stabilizer of any collection $P$: it consists of all permutations that (a) separately permute the elements of the $A_j$, (b) permute the remaining elements in $X - \cup_j A_j$, and (c) then permute the $A_j$ among themselves.

combinations[x_List, k_Integer, 0] := {{}};
combinations[x_List, k_Integer, m_Integer] := {};
combinations[x_List, k_Integer, m_Integer] /; 
   k m <= Length[x] && k >= 1 && m >= 1 := Block[{y, with, without},
   y = Prepend[#, First@x] & /@ Subsets[Rest@x, {k - 1}];
   with = Flatten[Table[Prepend[#, z] & /@ combinations[Complement[x, z], k, m - 1], {z, y}], 1];
   without = combinations[Rest@x, k, m];
   with~Join~without
   ];
combinationsCount[n_, k_, m_] := Multinomial @@ Append[ConstantArray[k, m], n  - k m] / m!

Examples

combinationsCount[6, 3, 2]

$10$

MatrixForm /@ combinations[{a, b, c, d, e, f}, 3, 2] 

$\begin{array}{lllll} \left( \begin{array}{ccc} a & b & c \\ d & e & f \end{array} \right) & \left( \begin{array}{ccc} a & b & d \\ c & e & f \end{array} \right) & \left( \begin{array}{ccc} a & b & e \\ c & d & f \end{array} \right) & \left( \begin{array}{ccc} a & b & f \\ c & d & e \end{array} \right) & \left( \begin{array}{ccc} a & c & d \\ b & e & f \end{array} \right) \\ \left( \begin{array}{ccc} a & c & e \\ b & d & f \end{array} \right) & \left( \begin{array}{ccc} a & c & f \\ b & d & e \end{array} \right) & \left( \begin{array}{ccc} a & d & e \\ b & c & f \end{array} \right) & \left( \begin{array}{ccc} a & d & f \\ b & c & e \end{array} \right) & \left( \begin{array}{ccc} a & e & f \\ b & c & d \end{array} \right) \end{array}$

combinationsCount[13, 3, 4]

$200200$

AbsoluteTiming[Length@combinations[Range@13, 3, 4]]

$\{5.9153384,200200\}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.