Why does this take so long time to run?

How do you improve the speed of this? It took me more than 10 minutes and is still running.
I want to gather them in pair of inverse elements.

states = Tuples[{True, False}, {16}]
Gather[states, ((Not /@ #1) == #2) &]

• I think that the reason is that states // Length yields 65536.
– user49048
Feb 23, 2022 at 17:31
• @DiSp0sablE_H3r0 do you have any idea to do it faster?
– hana
Feb 23, 2022 at 17:33
• not on the top of my head. perhaps useful links: mathematica.stackexchange.com/questions/215075/…
– user49048
Feb 23, 2022 at 17:34
• mathematica.stackexchange.com/questions/179042/…
– user49048
Feb 23, 2022 at 17:34
• @DiSp0sablE_H3r0 I think there are some ways to generate the pairs without doing Gather but I'm not exactly know how to do it.
– hana
Feb 23, 2022 at 17:36

You can generate all such pairs by using their symmetry

pairs[n_]:={{True,Sequence@@#},{False,Sequence@@(Not/@#)}}&/@Tuples[{True,False},{n-1}];


gatheredStates[n_]:= Gather[Tuples[{True, False}, {n}], ((Not /@ #1) == #2) &];

pairs[10] === gatheredStates[10]
(* True *)


though much faster

RepeatedTiming[pairs[16];]
(* 0.18793 sec *)

• Using 0 and 1 in place of False and True makes things just a little faster (about 15% faster): pairs[n_] := {{1, Sequence @@ #}, {0, Sequence @@ (1 - #)}} & /@ Tuples[{1, 0}, {n - 1}];.
– JimB
Feb 23, 2022 at 19:07

As an example, here are the binary numbers from 0 to 7:

Counting and pairing these up as shown above would achieve the same result when converted to Boolean values.

binpairs[n_] := {IntegerDigits[2^n - # - 1, 2, n],
IntegerDigits[#, 2, n]} & /@
Range[0, 2^(n - 1) - 1] /. {1 -> True, 0 -> False}


To compare equivalence with the answer by @Hausdorff:

binpairs[16] == pairs[16]


(*True*)

An advantage of using binary numbers is that each pair in the list is deterministic: i.e., Nothing needs to be pre-computed or stored.

Here is an alternative approach using 0 and 1 rather than False and True:

pairs[n_] := Module[{t},
t = Tuples[{0, 1}, {n}];
t = Transpose[{t, 1 - t}];
t = DeleteDuplicates[Sort[#] & /@ t]]

pairs[4]
(* {{{0, 0, 0, 0}, {1, 1, 1, 1}}, {{0, 0, 0, 1}, {1, 1, 1, 0}},
{{0, 0, 1, 0}, {1, 1, 0, 1}}, {{0, 0, 1, 1}, {1, 1, 0, 0}},
{{0, 1, 0, 0}, {1, 0, 1, 1}}, {{0, 1, 0, 1}, {1, 0, 1, 0}},
{{0, 1, 1, 0}, {1, 0, 0, 1}}, {{0, 1, 1, 1}, {1, 0, 0, 0}}} *)

RepeatedTiming[pairs[16];]
(* {0.100445, Null} *)


Stealing directly from @Syed 's answer only the first half of the tuples need to be examined which is must faster:

pairs[n_] := Module[{t},
t = Tuples[{0, 1}, {n}][[1 ;; 2^(n - 1)]];
t = Transpose[{t, 1 - t}]]

pairs[4]
(* {{{0, 0, 0, 0}, {1, 1, 1, 1}}, {{0, 0, 0, 1}, {1, 1, 1, 0}},
{{0, 0, 1, 0}, {1, 1, 0, 1}}, {{0, 0, 1, 1}, {1, 1, 0, 0}},
{{0, 1, 0, 0}, {1, 0, 1, 1}}, {{0, 1, 0, 1}, {1, 0, 1, 0}},
{{0, 1, 1, 0}, {1, 0, 0, 1}}, {{0, 1, 1, 1}, {1, 0, 0, 0}}} *)

RepeatedTiming[pairs[16];]
(* {0.0141504, Null} *)