# Creating pairs of non-intersecting set from a given set

Let's say I have a set {a,b,c,d} and I want to create a list of pairs {{a,b,c,d},{}},{{a,b,c},{d}},{{a,b,c},{}},... such that there is no intersection between each pair, and they do not need to use all the elements. The ordering does not matter. Below is my first attempt

Clear[a, b, c, d]
allsubsets = Subsets[{a, b, c, d}]
comp = Reverse[allsubsets](*get the complement*)
paired = Table[
{allsubsets[[i]], #} & /@ comp
, {i, 1, Length[allsubsets]}];
result = DeleteDuplicates[Flatten[paired, 1]]
Length[result]


However, there is still many repeating elements due to the ordering. And I generated a lot of redundant sets so the program is terribly inefficient. This will run (with 4 elements, but I hope it can be extended to more general case) about 10,000 times in the whole program, so the speed may be of interest. Thank you in advance!

Your result can be obtained using Tuples:

Tuples[allsubsets, 2] == Sort @ result


True

You can construct non-intersecting pairs directly from allsubsets:

pairs = Join @@ Table[{i, #} & /@ Subsets[Complement[{a, b, c, d}, i]], {i, allsubsets}];

Length @ pairs


81

Alternatively, you can use

pairs2 = Select[Tuples[allsubsets, 2], DisjointQ @@ #&]

pairs2 == pairs


True

• This does not agree with my understanding of OP's explanation, "such that there is no intersection between each pair". – C. E. Jun 21 '19 at 11:16
• @C.E, thank you; just added the missing piece. – kglr Jun 21 '19 at 11:33