3
$\begingroup$

Writing:

n = 3;
Tuples[{"min", "MAX"}, n]

I get:

{{"min", "min", "min"}, {"min", "min", "MAX"}, {"min", "MAX", "min"}, {"min", "MAX", "MAX"}, {"MAX", "min", "min"}, {"MAX", "min","MAX"}, {"MAX", "MAX", "min"}, {"MAX", "MAX", "MAX"}}

One way to duplicate this function is to fill in this table by columns. In fact, writing:

tuples = ConstantArray[0, {2^n, n}];
flag = 1;
For[j = 1, j <= n, j++,
    For[i = 1, i <= 2^n, i++,
        If[flag == 1,
           tuples = ReplacePart[tuples, {i, j} -> "min"],
           tuples = ReplacePart[tuples, {i, j} -> "MAX"]
          ];
        If[Mod[i, 2^(n - j)] == 0, flag = flag + 1];
        If[flag > 2, flag = 1]
       ]
   ];
tuples

I get:

{{"min", "min", "min"}, {"min", "min", "MAX"}, {"min", "MAX", "min"}, {"min", "MAX", "MAX"}, {"MAX", "min", "min"}, {"MAX", "min","MAX"}, {"MAX", "MAX", "min"}, {"MAX", "MAX", "MAX"}}

Now I would like to duplicate this function by filling in this table by rows. My first approach is the following:

tuples = ConstantArray[0, {2^n, n}];
For[i = 1, i <= 2^n, i++,
    For[j = 1, j <= n, j++,
        If[2^(j - 1) <= i <= 2^n/2^j,
           tuples = ReplacePart[tuples, {i, j} -> "min"],
           tuples = ReplacePart[tuples, {i, j} -> "MAX"]
          ]
       ]
   ];
tuples

which offers only the first correct column:

{{"min", "MAX", "MAX"}, {"min", "min", "MAX"}, {"min", "MAX", "MAX"}, {"min", "MAX", "MAX"}, {"MAX", "MAX", "MAX"}, {"MAX", "MAX","MAX"}, {"MAX", "MAX", "MAX"}, {"MAX", "MAX", "MAX"}}

Any idea to correct this code? Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ Why does the order in which you fill the matrix matter? $\endgroup$
    – m_goldberg
    Commented Sep 22, 2019 at 17:06
  • 1
    $\begingroup$ Mathematica stores matrices in row-order, so proceeding by rows will always be more efficient than proceeding be columns. Trying to force a computation into column-order will only slow the computation down. $\endgroup$
    – m_goldberg
    Commented Sep 22, 2019 at 17:18

2 Answers 2

3
$\begingroup$

Noticing that going row-by-row, we're essentially counting in binary (with "min" as 0 and "MAX" as 1), we see that we can use BitAnd[i - 1, 2^(n - j)] == 0 as condition:

n = 3;

tuples = ConstantArray[0, {2^n, n}];
For[i = 1, i <= 2^n, i++, 
 For[j = 1, j <= n, j++, 
  If[BitAnd[i - 1, 2^(n - j)] == 0, 
   tuples = ReplacePart[tuples, {i, j} -> "min"],
   tuples = ReplacePart[tuples, {i, j} -> "MAX"]
   ]
 ]
];
tuples
(* {{"min", "min", "min"}, {"min", "min", "MAX"}, {"min", "MAX", "min"}, 
    {"min", "MAX", "MAX"}, {"MAX", "min", "min"}, {"MAX", "min", "MAX"},
    {"MAX", "MAX", "min"}, {"MAX", "MAX", "MAX"}} *)

Or, more concise:

tuples = ConstantArray[0, {2^n, n}];
Do[
  tuples = ReplacePart[
    tuples,
    {i, j} -> If[BitAnd[i - 1, 2^(n - j)] == 0, "min", "MAX"]
    ],
  {i, 2^n},
  {j, n}
  ];
tuples
(* same output *)

The condition works by checking the $(n-j)$-th bit of $i-1$ using BitAnd:

  • $n-j$ instead of e.g. $j$ because the zeroth bit is the $n$-th column, and the $n-1$-th bit is the first column
  • The $-1$ in $i-1$ is needed since row indices start at $1$, but the counting starts at $0$

Note: Since the condition is completely stateless (i.e. there is no flag variable or similar), we can simply swap the iteration indices to change the filling order:

tuples = ConstantArray[0, {2^n, n}];
Do[
  tuples = ReplacePart[
    tuples,
    {i, j} -> If[BitAnd[i - 1, 2^(n - j)] == 0, "min", "MAX"]
    ],
  {j, n},
  {i, 2^n}
  ];
tuples
(* same output *)
$\endgroup$
3
  • 1
    $\begingroup$ BitAnd is essentially the bit wise AND operator from most other languages (e.g. & in C and related languages). Also, what exactly do you mean by "not pre-packaged in some environments"? $\endgroup$
    – Lukas Lang
    Commented Sep 22, 2019 at 17:38
  • $\begingroup$ Out of curiosity: can you give an example of such a language without BitAnd equivalent? $\endgroup$
    – Lukas Lang
    Commented Sep 22, 2019 at 17:50
  • 1
    $\begingroup$ I think you don't need to worry about this particular operator - I think I have yet to come across a language without bit wise operators $\endgroup$
    – Lukas Lang
    Commented Sep 22, 2019 at 18:04
3
$\begingroup$

Lukes answer is excellent but it can be improved. This version is faster as well as more concise.

n = 3;
tuples = ConstantArray[0, {2^n, n}];
Do[
  tuples[[i, j]] = If[BitAnd[i - 1, 2^(n - j)] == 0, "min", "MAX"], 
  {j, n}, {i, 2^n}];
tuples // MatrixForm

matrix

Your For-loop solution can also be improved by applying the same ideas.

flag = 0;
Do[
  If[flag == 0, tuples[[i, j]] = "min", tuples[[i, j]] = "MAX"]; 
  If[Mod[i, 2^(n - j)] == 0, flag = Mod[flag + 1, 2]],
  {j, n}, {i, 2^n}];
$\endgroup$
0

Your Answer

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

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