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

Question

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!

Answer 1

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][1]
(* {{{0, 0}, {0, 0}}, {{0, 0}, {0, 0}}, {{0, 0}, {0, 0}}} *)

and the last one is

tuple[2,3][4096]
(* {{{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.

Answer 2

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.