3
$\begingroup$

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) &]
Improve this question
$\endgroup$
5
  • $\begingroup$ I think that the reason is that states // Length yields 65536. $\endgroup$
    – user49048
    Feb 23, 2022 at 17:31
  • $\begingroup$ @DiSp0sablE_H3r0 do you have any idea to do it faster? $\endgroup$
    – hana
    Feb 23, 2022 at 17:33
  • $\begingroup$ not on the top of my head. perhaps useful links: mathematica.stackexchange.com/questions/215075/… $\endgroup$
    – user49048
    Feb 23, 2022 at 17:34
  • $\begingroup$ mathematica.stackexchange.com/questions/179042/… $\endgroup$
    – user49048
    Feb 23, 2022 at 17:34
  • $\begingroup$ @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. $\endgroup$
    – hana
    Feb 23, 2022 at 17:36

3 Answers 3

Reset to default
10
$\begingroup$

You 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 *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ 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}];. $\endgroup$
    – JimB
    Feb 23, 2022 at 19:07
9
$\begingroup$

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

enter image description here

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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} *)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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