# Duplicate Tuples in two different ways

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!

• Why does the order in which you fill the matrix matter? – m_goldberg Sep 22 '19 at 17:06
• @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. – TeM Sep 22 '19 at 17:09
• 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. – m_goldberg Sep 22 '19 at 17:18

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 *)

• 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! – TeM Sep 22 '19 at 17:33
• 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"? – Lukas Lang Sep 22 '19 at 17:38
• 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. – TeM Sep 22 '19 at 17:41
• Out of curiosity: can you give an example of such a language without BitAnd equivalent? – Lukas Lang Sep 22 '19 at 17:50
• 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 – Lukas Lang Sep 22 '19 at 18:04

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


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}];

• You are really kind and at the same time brilliant, thanks for sharing your immense knowledge! – TeM Sep 22 '19 at 17:47