4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Can you use some sort of combinatorics argument to work it out without computers? ((2^n)^n)^m is enormous for n=m=5 $\endgroup$ – gpap Feb 3 '15 at 13:33
  • $\begingroup$ 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. $\endgroup$ – user16153 Feb 3 '15 at 13:46
  • $\begingroup$ in which case, unless you specify the condition, it's not easy to answer this $\endgroup$ – gpap Feb 3 '15 at 13:51
  • $\begingroup$ See edit. Thanks! $\endgroup$ – user16153 Feb 3 '15 at 14:21
  • $\begingroup$ Will Count[] suffice? $\endgroup$ – David G. Stork Feb 3 '15 at 17:10
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.