# Partition a set into subsets of size $k$

Given a set $\{a_1,a_2,\dots,a_{lk}\}$ and a positive integer $l$, how can I find all the partitions which includes subsets of size $l$ in Mathematica? For instance, given `{1,2,3,4}` and `l=2`, the output should be:

$$\text{Partition 1: }\{1,2\},\{3,4\}$$ $$\text{Partition 2: }\{1,3\},\{2,4\}$$ $$\text{Partition 3: }\{1,4\},\{2,3\}$$

In Mathematica notation:

````{
 {{1,2},{3,4}},
 {{1,3},{2,4}},
 {{1,4},{2,3}}
}
````

Edit: Another example for `l=3`, and `{1,2,3,4,5,6}`:

````{
 {{1, 2, 3}, {4, 5, 6}}, 
 {{1, 2, 4}, {3, 5, 6}}, 
 {{1, 2, 5}, {3, 4, 6}}, 
 {{1, 2, 6}, {3, 4, 5}},
 {{1, 3, 4}, {2, 5, 6}},
 {{1, 3, 5}, {2, 4, 6}}, 
 {{1, 3, 6}, {2, 4, 5}},
 {{1, 4, 5}, {2, 3, 6}},
 {{1, 4, 6}, {2, 3, 5}},
 {{1, 5, 6}, {2, 3, 4}}
}
````
-

@murray: I think it would be clear if you read the example. The size of the set is $kl$, so it can be simply partitioned into $k$ subsets of size $l$. I am looking for all such partitions. – Mohsen Mar 15 '12 at 23:57
@Mohsen, yes, I know you use $k$ and $l$ but unfortunately in your example, $k$ = $l$ = 2. Which is why it's hardly the best example one might start from. – murray Mar 16 '12 at 3:35
@murray: I just added a new example with $k=2$ and $l=3$. – Mohsen Mar 16 '12 at 17:57

## 5 Answers

Try with

````partitions[list_, l_] := Join @@
  Table[
    {x, ##} & @@@ partitions[list ~Complement~ x, l],
    {x, Subsets[list, {l}, Binomial[Length[list] - 1, l - 1]]}
  ]

partitions[list_, l_] /; Length[list] === l := {{list}}
````

The list must have a length multiple of l

-

I believe this is correct. It is based on `BellList` from Robert M. Dickau.

````Module[{n = 4, q = 2, r, BellList},
 r = n/q;
 BellList[1] = {{{1}}};
 BellList[n_Integer?Positive] :=
  Join @@ (ReplaceList[#,
         {{b___, {S : Repeated[_, {1, q - 1}]}, a___} :> {b, {S, n}, a},
         {S : Repeated[_, {1, r - 1}]} :> {S, {n}}}
        ] & /@ BellList[n - 1]);
 BellList[n]
]
````

You'll have to make sure `n` is divisible by `q` or adapt it to behave as you want. Also, this uses natural numbers for the set, but these in turn can be used as indices to extract elements from the working set.

-

+1 for throwing in the formal name of the problem. I had a hard time googling it. – István Zachar Mar 15 '12 at 20:06

Use `Subsets`:

````Subsets[{1, 2, 3, 4}, {2}]
````

Gives:

````{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
````

````a = {1, 2, 3, 4};
DeleteDuplicates[Sort /@ (Sort /@ Partition[#, 2] & /@ Permutations[a, {4}])]
````

which outputs

```` {{{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}}
````
-

1
Actually, I am looking for partitions, not permutations. So, $\{1,2\},\{3,4\}$ is one partition and $\{1,3\},\{2,4\}$ is another one. I just edited the question to clarify this. – Mohsen Mar 15 '12 at 19:12
How's this version? – Eli Lansey Mar 15 '12 at 19:40

Really lazy search through all partitioned permutations:

````set = {1, 2, 3, 4};
Union[Sort /@ (Sort /@ Partition[#, 2] & /@ 
     Permutations[set, {4}])]
````
````{
{{1, 2}, {3, 4}},
{{1, 3}, {2, 4}},
{{1, 4}, {2, 3}}
}
````

And a more economic one:

````set = {1, 2, 3, 4};
subsets = Subsets[set, {2}];
Table[{i, Cases[subsets, _?(Union[#, i] === set &)]}, {i, 
   Take[subsets, Length@subsets/2]}]
````
````{
{{1, 2}, {3, 4}},
{{1, 3}, {2, 4}},
{{1, 4}, {2, 3}}
}
````

This generates all the subsets of size 2 (6 of them), and scans through them one-by-one to find their complement in the same list. Since it can be assumed that the output of `Subsets` is regular, the above can be simplified to simply split the `subsets` list to two, and merging the first half with the reversed second half.:

````n = Length@subsets;
MapThread[List, {Take[subsets, n/2], Take[Reverse@subsets, n/2]}]
````
-

Thanks István, actually I am looking for a solution for a general $l$, not only $l=2$. So, your last solution doesn't help, but the other ones looks great. I tested them for $l=3$ and $k=3$ (i.e., 9 numbers) and they work perfect, but for 12 numbers they don't. Is there any way to solve the issue or there are too many partitions with $l=3$ and $k=4$, ummm? – Mohsen Mar 15 '12 at 19:48
Yes, I have realized that, so I am now working on a general solution. For the worst, one can do a partial tree-traversal by fixing the first digit and changing the next one, fixing it and changing the next one, etc... I'm pretty sure that before I could solve this, others will post some beautiful answers. – István Zachar Mar 15 '12 at 19:59

You might start with the `Combinatorica` add-on function `SetPartitions` and then select those partitions satisfying the condition about the size of their members. But this may be too "extravagant" an approach when the original set size becomes a bit big.

-
lang-mma
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8423462510108948, "perplexity_flag": "middle"}