title: Enumerate partitions of a set into subsets of equal size
body: <p>I have a set and I want to partition it into sub-set containing equal number of element.</p>
  
  <p>I am looking for a fast algorithm and preferably not heuristic one.</p>
  
  <p><strong>Hint:</strong></p>
  
  <pre><code>if  n= number of elements in the main set
      l= number of elements in each subset 
  </code></pre>
  
  <p><strong>A brute force algorithm is:</strong></p>
  
  <blockquote>
    <p>1-x &lt;-All combinations of n things taken l  at a time without
    repetition. |x|=nCl=n!/(l!*(n-l)!)<br>
    2-y &lt;-All
    combinations of x things taken n at a time without repetition. |y|=xCn</p>
    
    <p>3-Select subsets in y such as there is no any overlap within their
    elements.</p>
  </blockquote>
  
  <p>The number of answers is:</p>
  
  <pre><code>n!/(l!^(n/l)*(n/l)!)
  </code></pre>
  
  <p>For instance if  <code>S={a,b,c,d}</code> and if subsets with 2 elements to partition set S is desired:</p>
  
  <p>The set x is  :  </p>
  
  <pre><code>   (a,b),(a,c),(a,d),(b,c),(b,d),(c,d)
  </code></pre>
  
  <p>The set y (potential answers)is  :  </p>
  
  <pre><code>{(a,b),(a,c)}
  {(a,b),(a,d)}
  {(a,b),(b,c)}
  {(a,b),(b,d)}
  {(a,b),(c,d)}       
  {(a,c),(a,d)}
  {(a,c),(b,c)}
  {(a,c),(b,d)}
  {(a,c),(c,d)}
  {(a,d),(b,c)}   
  {(a,d),(b,d)} 
  {(a,d),(c,d)}   
  {(b,c),(d,d)}   
  {(b,c),(c,d)}   
  {(b,d),(c,d)}   
  </code></pre>
  
  <p>and the correct answers are :  </p>
  
  <pre><code>S1={(a,b),(c,d)}
  S2={(a,c),(b,d)}
  S3={(a,d),(b,c)}
  </code></pre>
  
  <p>The mentioned algorithm is useful only when n is small. 
  For instance when:</p>
  
  <pre><code> n=90, l=3 =&gt;
  |x|=117480 
  |y|=1.28827732e+318
  and the number of correct answers is `2.533601e+82`.
  </code></pre>
  
  <p>So the algorithm is not practical for the most case due to time performance and memory issues.</p>
  
  <p>Even having and running an efficient algorithm would be time consuming as the number of results is a lot. For instance in the above problem the number of answers = <code>2.533601e+82</code></p>
  
  <p>I am not expertise in the set theory so maybe it is  a well known problem.</p>
  
  <p>Thanks for your help.</p>