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).

  • $\begingroup$ The number of letters change or you will just use 4? $\endgroup$
    – Spawn1701D
    Commented Apr 18, 2013 at 18:27
  • $\begingroup$ Aren't they the permutations, properly splitted? $\endgroup$ Commented Apr 18, 2013 at 18:33
  • $\begingroup$ @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. $\endgroup$
    – whuber
    Commented Apr 18, 2013 at 18:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Commented Apr 19, 2013 at 3:22
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 19, 2013 at 12:55

1 Answer 1


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];
combinationsCount[n_, k_, m_] := Multinomial @@ Append[ConstantArray[k, m], n  - k m] / m!


combinationsCount[6, 3, 2]


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]


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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