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) &]
Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this communityYou can generate all such pairs by using their symmetry
pairs[n_]:={{True,Sequence@@#},{False,Sequence@@(Not/@#)}}&/@Tuples[{True,False},{n-1}];
This leads to the same result as your code
gatheredStates[n_]:= Gather[Tuples[{True, False}, {n}], ((Not /@ #1) == #2) &];
pairs[10] === gatheredStates[10]
(* True *)
though much faster
RepeatedTiming[pairs[16];]
(* 0.18793 sec *)
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}];
.
$\endgroup$
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} *)
states // Length
yields65536
. $\endgroup$