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$
  • 1
    $\begingroup$ Why does the order in which you fill the matrix matter? $\endgroup$ – m_goldberg Sep 22 '19 at 17:06
  • $\begingroup$ @m_goldberg: if we limit ourselves to filling a matrix I agree that one way is as good as another. However, if this algorithm is applied in other contexts, it may be much more efficient to proceed by rows. Unfortunately, I have not found this approach in any book. $\endgroup$ – TeM Sep 22 '19 at 17:09
  • 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 Sep 22 '19 at 17:18
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$
  • $\begingroup$ I sometimes remain speechless, I would never have arrived! Now I will have to study the BitAnd function, because in some environments it is not pre-packaged. In any case, magnificent, thank you! $\endgroup$ – TeM Sep 22 '19 at 17:33
  • 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 Sep 22 '19 at 17:38
  • $\begingroup$ In Mathematica, Excel, ... it is sufficient to make use of BitAnd, because it is already present in their library; in other programs, this function must be constructed using For, While and If commands. $\endgroup$ – TeM Sep 22 '19 at 17:41
  • $\begingroup$ Out of curiosity: can you give an example of such a language without BitAnd equivalent? $\endgroup$ – Lukas Lang Sep 22 '19 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 Sep 22 '19 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$
  • $\begingroup$ You are really kind and at the same time brilliant, thanks for sharing your immense knowledge! $\endgroup$ – TeM Sep 22 '19 at 17:47

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.