Consider a $3d$ lattice latin hypercube with $n$ steps in each dimension, so it has $n^3$ positions. Coordinates $X, Y, Z \in \{1,2,...n\}$. I want to find all of the permutations of them where they add to $S=3(n+1)/2$.
The number of permutations is only non-zero when $n$ is odd, and is A002047 from the Sloane sequence library. I've brute forced my way to generating the permutations via Permutations
and Subsets
and it works alright, but wanted to see if FindInstance
could do better. It's easier to define the problem.
Here is what I have:
nn = 3;
ss = 3 (num + 1)/2;
yvars = Table[y[i], {i, nn}]; (* instantiate the y[] and z[] variables *)
zvars = Table[z[i], {i, nn}];
xvars = Table[x[i] = i, {i, nn}]; (* just set these to {1,...,nn} *)
(* Force Z to be a permutation *)
betweenZ = 1 <= zvars <= nn;
unequalZ = Unequal @@ zvars;
(* same for Y *)
betweenY = 1 <= yvars <= nn;
unequalY = Unequal @@ yvars;
(* force the sums to equal S *)
sumeqns = xvars + yvars + zvars == Table[ss, {nn}]; (* sum properly *)
rules = FindInstance[{betweenZ,unequalZ, betweenY, unequalY, sumeqns},
Join @@ {yvars, zvars},
Integers,
20]
Length@rules
(* 2 *)
This works fine, except it is slow. With $n=7$ it takes 22 seconds on my machine to get a single permutation. Using my brutish force approach, I can get all 244 permutations for when $n=9$ in about 3 seconds.
I was wondering if there were other ways to pass the constraints into FindInstance
that might be more suitable for processing in its innards. Thoughts?
Edit
Turns out this is the same problem as explored in 1966, where the authors used CDC3200 computer to explore the number of permutations.
ARRAYS AND BROOKS B. T. BENNETT and R. B. POTTS