# How to check whether elements of a list meet a condition without generating the whole list first?

I have to find the number of elements satisfying a given condition from the set:

Tuples[Tuples[Tuples[{0,1},n],n],m]


The condition for $n=3,m=3$ is:

h[{{{x1_, x2_, x3_}, {x4_, x5_, x6_}, {x7_, x8_, x9_}}, {{y1_, y2_,
y3_}, {y4_, y5_, y6_}, {y7_, y8_, y9_}}, {{z1_, z2_, z3_}, {z4_,
z5_, z6_}, {z7_, z8_, z9_}}}]=1


where,

h[{{{x1_, x2_, x3_}, {x4_, x5_, x6_}, {x7_, x8_, x9_}}, {{y1_, y2_,
y3_}, {y4_, y5_, y6_}, {y7_, y8_, y9_}}, {{z1_, z2_, z3_}, {z4_,
z5_, z6_}, {z7_, z8_, z9_}}}] =  Piecewise[{{1,
f[x1 + y1 + z1] + f[x4 + y4 + z4] + f[x7 + y7 + z7] !=
f[x2 + y2 + z2] + f[x5 + y5 + z5] + f[x8 + y8 + z8] &&
f[x2 + y2 + z2] + f[x5 + y5 + z5] + f[x8 + y8 + z8]  !=
f[x3 + y3 + z3] + f[x6 + y6 + z6] + f[x9 + y9 + z9] &&
f[x1 + y1 + z1] + f[x4 + y4 + z4] + f[x7 + y7 + z7] !=
f[x3 + y3 + z3] + f[x6 + y6 + z6] + f[x9 + y9 + z9]}}, 0]


I don't have to output which ones satisfy the condition - I just need to count them. Currently, I generate the whole set and use the $Select$ function (together with $Length$). However, for $n=4,m=5$ this is already too large for Mathematica to run.

I am thinking there must be a (slow, but memory efficient) way to construct $Tuples[Tuples[Tuples[{0,1},n],n],m]$ one element at a time and check for each element whether it satisfies the condition or not.

I am mostly interested in $n<=5$ and $m<=5$.

Thank you in advance!

• Can you use some sort of combinatorics argument to work it out without computers? ((2^n)^n)^m is enormous for n=m=5 – gpap Feb 3 '15 at 13:33
• There is a way of trimming down $Tuples[Tuples[{0,1},n],n]$ for my intended application quite significantly, but I would still need a way of generating the outer Tuples in an iterative way. – user16153 Feb 3 '15 at 13:46
• in which case, unless you specify the condition, it's not easy to answer this – gpap Feb 3 '15 at 13:51
• See edit. Thanks! – user16153 Feb 3 '15 at 14:21
• Will Count[] suffice? – David G. Stork Feb 3 '15 at 17:10

## 2 Answers

Is this what you need to generate your super tuples one by one ? I think this should work :

tuple[n_, m_][i_] := Partition[Partition[IntegerDigits[i - 1, 2, m*n^2], n], n]


### Test

For example when n=2and m=3, you have 2^(m*n^2)=4096 super-tuples, and you call the first one with :

tuple[2,3]
(* {{{0, 0}, {0, 0}}, {{0, 0}, {0, 0}}, {{0, 0}, {0, 0}}} *)


and the last one is

tuple[2,3]
(* {{{1, 1}, {1, 1}}, {{1, 1}, {1, 1}}, {{1, 1}, {1, 1}}} *)


You can check that :

n=2; m=3;

tuple[n, m] /@ Range[2^(m*n^2)] == Tuples[Tuples[Tuples[{0, 1}, n], n], m]

(* True *)


It should work with all n and m.

Speed might be a problem because it seems much (50x) slower that with Tuples ... However you can at least parallelize the computations.

It is the first time when I see nested Tuples. However, the output is quite simple:

Tuples[Tuples[Tuples[{0,1},n],n],m]


produces a list of all possible $m\times n\times n$ arrays with elements $0$ or $1$. To sum up a certain function h we can use the following function

count[h_, d_] := Sum @@ Prepend[{#, 0, 1} & /@ Flatten@#, h@#] &@Array[Unique[] &, d]


Or its compiled version

countC[h_, d_] := Compile @@ Hold[{}, Sum@##, CompilationTarget -> "C",
RuntimeOptions -> "Speed"] & @@
Prepend[{#, 0, 1} & /@ Flatten@#, h@#] &@Array[Unique[] &, d]


A toy example with counting matrices with only one $1$:

count[Boole[Total@Flatten@# == 1] &, {3, 3, 3}] // AbsoluteTiming
(* {25.091417, 27} *)

c = countC[Boole[Total@Flatten@# == 1] &, {3, 3, 3}];
c[] // AbsoluteTiming
(* {1.012880, 27} *)


Note, that the case $n=4$ and $m=5$ has $2^{80}$ matrices. It is impossible to calculate this sum even without storing a whole list.