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]]

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


You can construct non-intersecting pairs directly from allsubsets:

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

Length @ pairs


Alternatively, you can use

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

pairs2 == pairs


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.