# Find all disjoint subsets of equal length

Suppose that $A$ is a list with $n$ elements where $n$ is even. I want to write a function that returns all pairs $(A_1,A_2)$ where the sets $A_1$ and $A_2$ each have length $\frac{n}{2}$, $A_1 \cap A_2=\emptyset$, and $A_1,A_2 \subset A$.

• In "pair" order matters? – Kuba Mar 26 '15 at 15:07
• I assume you meant distinct elements based on accepted answer? – ciao Mar 26 '15 at 23:41

I'm assuming in A_1 A_2 pair, order matters:

set = Range;

Transpose[{#, Reverse@#}] & @ Subsets[#, {Length[#]/2}] & @ set

{{{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}}, {{2, 3,
4}, {1, 5, 6}}, {{2, 3, 5}, {1, 4, 6}}, {{2, 3, 6}, {1, 4,
5}}, {{2, 4, 5}, {1, 3, 6}}, {{2, 4, 6}, {1, 3, 5}}, {{2, 5,
6}, {1, 3, 4}}, {{3, 4, 5}, {1, 2, 6}}, {{3, 4, 6}, {1, 2,
5}}, {{3, 5, 6}, {1, 2, 4}}, {{4, 5, 6}, {1, 2, 3}}}


If pair isn't ordered you can take halof of above or spare some memory doing:

With[{l = Length[#]},
Transpose[{#, Reverse@#2}] & @@
Partition[Subsets[#, {l/2}], Binomial[l, l/2]/2]] &@set

• This is some nice tight code, but I have one issue. Once the size of the set get big (say 20 elements) speed an memory become an issue. Any ideas on how to handle this? It would be ideal if I could do this for set of size100 or better. I also was not explicit, I don't care about order. – Wintermute Mar 26 '15 at 17:05
• @Wintermute for really big data you can iterate through subsets with the third argument of Subsets and save them to the file. Depends of the final goal. – Kuba Mar 26 '15 at 17:20
• @Kuba: Seeing as there will be 50445672272782096667406248628 disjoint paired subsets for a list of 100, not going to happen... ;-) – ciao Mar 27 '15 at 0:04
• No up-votes? Let me fix that. – Mr.Wizard Jan 30 '16 at 21:52
• @Mr.Wizard Thanks, and you are right, this is specific case and I'm abusing the fact the partition is done in half. – Kuba Jan 30 '16 at 21:53

@Wizard, @Kuba, Sorry I do not have sufficient reputation for adding comments, therefore I take the liberty to post it as an Answer. Your solution result not only contains (A1,A2) but also contains (A2,A1), therefore // Take[#, Length @ #/2] & needs to be added in order to take only (A1,A2). :)

• This is why I've asked a question if a pair is ordered. – Kuba Mar 26 '15 at 17:21

If order does not matter,

Clear[splitList]

splitList[
list_?(VectorQ[#] && EvenQ[Length[list]] &)] :=
Module[{a1, a2, a3, len = Length[list]},
a1 = Subsets[list, {len/2}];
a2 = Complement[list, #] & /@ a1;
a3 = Transpose[{a1, a2}];
Union[a3, SameTest ->
(Sort[Sort /@ #1] === Sort[Sort /@ #2] &)]]

splitList[{e1, e2, e3, e4, e5, e6}]


{{{e1, e2, e3}, {e4, e5, e6}}, {{e1, e2, e4}, {e3, e5, e6}}, {{e1, e2, e5}, {e3, e4, e6}}, {{e1, e2, e6}, {e3, e4, e5}}, {{e1, e3, e4}, {e2, e5, e6}}, {{e1, e3, e5}, {e2, e4, e6}}, {{e1, e3, e6}, {e2, e4, e5}}, {{e1, e4, e5}, {e2, e3, e6}}, {{e1, e4, e6}, {e2, e3, e5}}, {{e1, e5, e6}, {e2, e3, e4}}}

splitList[{j, a, l, b}]


{{{a, b}, {j, l}}, {{a, l}, {b, j}}, {{j, a}, {b, l}}}

• I don't quite get this Union. Could you explain why you need this? – Kuba Mar 26 '15 at 15:18
• @Kuba - it is used to eliminate equivalent pairs. To be independent of the internal workings of Subsets and Complement, it makes no assumptions about how Subsets or Complement returns their results. – Bob Hanlon Mar 26 '15 at 16:01

I would suggest using a combination of Subsets and Complement, two basic set operations in Mathematica. Here is an example code, you should be able to transfer that to any sort of list on your own:

(*create list*)
list = {1, 2, 3, 4, 5, 6, 7, 8};

(*create all subsets of length n/2*)
subsets = Subsets[list, {Length[list]/2}];

(*create the corresponding complements*)
complements = Complement[list, #] & /@ subsets;

(*combine each subset with its corresponding complement*)
output = Transpose@{subsets, complements};


output[[i]] then contains one specific pair of complements $(A_1,A_2)$.

• FYI, the last operation can be done with Transpose. – Kuba Mar 26 '15 at 15:19
• Sure, wasn't thinking much at the time of writing. Transpose is way faster, so I will edit it. – Wizard Mar 26 '15 at 21:45