7
$\begingroup$

I want to generate $n$ by $n$ binary arrays, and then reduce the output from those arrays by performing a number of permutations and eliminating duplicates. The problem is that the number of arrays increases as $2^{n^2}$, so storing every tuple in memory and comparing each permutation is impractical for $n>4$.

A working solution when $n<4$ is given here: Reduce the output from tuples by including symmetry?.

My questions is: how can I generate $n$ by $n$ binary arrays and eliminate duplicates (as defined by certain permutations) in a memory efficient manner?

For instance, is it possible to generate a few tuples at a time, run the permutations, check for duplicates, and then continue generating the remaining tuples?

P.S. I asked a different version of this question here: Constructing and Reducing Tuples in a Memory Efficient Manner, and have been unable to implement the solution given here: Memory efficient generation and selection of tuples.

$\endgroup$
4
$\begingroup$

I think you can do something with these identities:

Table[Partition[IntegerDigits[i, 2, 4], 2, 2], {i, 0, 2^4 - 1}] === Tuples[{0, 1}, {2, 2}]

Table[Partition[IntegerDigits[i, 2, 9], 3, 3], {i, 0, 2^9 - 1}] === Tuples[{0, 1}, {3, 3}]

So in general, you can say that this is True:

Table[Partition[IntegerDigits[i, 2, (n*n)], n, n], {i, 0, 2^(n*n) - 1}] === Tuples[{0, 1}, {n, n}]

(I checked this up to 5).

But this then gives you a way to just get any individual one:

f[n_, i_] := Partition[IntegerDigits[i, 2, (n*n)], n, n]

E.g.

f[10, 4938742893] //MatrixForm

Gives:

enter image description here

Hope this helps.

$\endgroup$
  • $\begingroup$ f[start_Integer, howMany_Integer, n_Integer] := Partition[#, n] & /@ Table[IntegerDigits[i, 2, n^2], {i, start, start + howMany - 1}] /; start >= 0 && howMany >= 1 && n > 0 && 0 < start + howMany - 1 <= 2^n^2 - 1; MatrixForm /@ f[0, 13, 2] $\endgroup$ – Dr. belisarius Mar 3 '16 at 2: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.