Find all disjoint subsets of equal length

Suppose that AA is a list with nn elements where nn is even. I want to write a function that returns all pairs (A1,A2)(A_1,A_2) where the sets A1A_1 and A2A_2 each have length n2\frac{n}{2}, A1∩A2=∅A_1 \cap A_2=\emptyset, and A1,A2⊂AA_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

=================

4 Answers
4

=================

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

set = Range[6];

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

1

 

@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 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 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 (A1,A2)(A_1,A_2).

1

 

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