Allocating a huge boolean array fails

[jk22]

In fact I already checked for binary domains. It can generate 3/4 of the number of f's.(f image domain is always considered with 2 values only)

But my suspiscion was that since the number of possible compositions over number of f's is $2^{n^2}n^{2n^2}/2^{n^3}$ there is a potential anomaly at values of n being 3,4,5. But I just checked for 3 and there is no surprise.

 

[wle]

I wonder if its possible to count the functions without exhaustive search on a computer.

You could potentially reduce the number of possibilities you need to search through. For instance, if you can write $f(x, y, z) = m \bigl( g(x, z), h(y, z) \bigr)$ then you can express the same function $f$ as $f(x, y, z) = m' \bigl( g'(x, z), h'(y, z) \bigr)$ where $$\begin{eqnarray}
m'(x, y) &=& m \bigl( \pi^{-1}(x), \pi'^{-1}(y) \bigr) \,, \\
g'(x, z) &=& \pi \bigl( g(x, z) \bigr) \,, \\
h'(y, z) &=& \pi' \bigl( h(y, z) \bigr)
\end{eqnarray}$$ and $\pi$ and $\pi'$ are arbitrary permutations $\{0, 1, 2\} \to \{0, 1, 2\}$. So if you can avoid counting possibilities that are related to each other by permutations like this then this reduces the number of possibilities you need to search through by a factor of around $(3!)^{2} = 36$. (It won't be exactly 36 because there are some functions that are the same under certain permutations. For instance, if $g(x, z) = 0$ for all $x, z$ then a permutation $\pi$ that swaps 1 and 2 doesn't change anything.) One way to do this is to impose constraints on the form of $g$ and $h$. For instance, write the different evaluations of $g$ in a certain order, e.g., $$\begin{equation}
g(0, 0),\, g(0, 1),\, g(0, 2),\, g(1, 0),\, g(1, 1),\, g(1, 2),\, g(2, 0),\, g(2, 1),\, g(2, 2) \,.
\end{equation}$$ You could exploit the symmetry under permutations to impose that $g(0, 0) = 0$ and that $g(x, z) = 1$ for the first $g(x, z)$ appearing in the list for which $g(x, z) \neq 0$, if there is one. I.e., consider only functions $g$ for which the list above starts with one or more 0s, then a 1, then any numbers in $\{0, 1, 2\}$ (and do the same for $h$).

 

[I like Serena]

this reduces the number of possibilities you need to search through by a factor of around $(3!)^{2} = 36$.

Building on this approach, I think we can do a little better by setting f(0,0,0)=g(0,0)=h(0,0)=0, which is good for a reduction of $3^3=27$.
And additionally only set f(x,y,z)=1, respectively g(x,z)=1, and h(y,z)=1 for the first applicable value that is $\ne 0$. That should be good for another reduction by a factor of $2^3=8$ for a total of $216$.
It won't affect the logic, and it won't affect the proportions.

Furthermore, getting back to the original reason for this thread, we don't need to allocate all that much memory do we?
We only need to iterate over all possibilities for f, g, and h, and we only need to keep one of each in memory at a time.
It remains a problem that the number of evaluations to make is so big

 

[jk22]

Yes if $n=4$ it is already out of reach but I think this ratio is decreasing as n increases but I have no proof. In fact it needs an exhaustive search only for $3,4,5$

What I noticed is for $n=2$ we can decompose any $f$ with 5 functions in the form $g(h(k(x,z),l(y,z)),m(x,z))$

But I don't know if it is always possible to decompose in functions of only $(x,z)$ and $(y,z)$, which is a locality condition, for higher n.

 

[wle]

An addition: I don't know about ratios/counting, but if the question is whether any $f$ can be written $f(x, y, z) = m \bigl( g(x, z), h(y, z) \bigr)$ as specified above then I think it's not too difficult to engineer examples where this will not work.

Here's an example. Suppose we have a function which, for $z = 0$, gives $$\begin{equation}
f(x, y, 0) = \begin{cases}
0 &\text{if } x = y \\
1 & \text{if } x \neq y
\end{cases} \,.
\end{equation}$$ Looking at some of the values you can notice that $$\begin{eqnarray}
f(0, 0, 0) \neq f(1, 0, 0) &\Rightarrow& m \bigl( g(0, 0), h(0, 0) \bigr) \neq m \bigl( g(1, 0), h(0, 0) \bigr) \,, \\
f(0, 0, 0) \neq f(2, 0, 0) &\Rightarrow& m \bigl( g(0, 0), h(0, 0) \bigr) \neq m \bigl( g(2, 0), h(0, 0) \bigr) \,, \\
f(1, 1, 0) \neq f(2, 1, 0) &\Rightarrow& m \bigl( g(1, 0), h(1, 0) \bigr) \neq m \bigl( g(2, 0), h(1, 0) \bigr) \,.
\end{eqnarray}$$ These in turn are only possible if (respectively) $$\begin{eqnarray}
g(0, 0) &\neq& g(1, 0) \,, \\
g(0, 0) &\neq& g(2, 0) \,, \\
g(1, 0) &\neq& g(2, 0) \,,
\end{eqnarray}$$ i.e., $g(0, 0)$, $g(1, 0)$, and $g(2, 0)$ must all be different from each other. Using the symmetry under permutations that I mentioned in my previous post, we can set $g(x, 0) = x$ without loss of generality. Similarly, we can also choose $h(y, 0) = y$. This means that, for $z = 0$, the decomposition $f(x, y, z) = m \bigl( g(x, z), h(y, z) \bigr)$ simplifies to $f(x, y, 0) = m(x, y)$. In other words, without loss of generality, we can take $m$ to be the function $$\begin{equation}
m(x, y) = \begin{cases}
0 &\text{if } x = y \\
1 & \text{if } x \neq y
\end{cases} \,,
\end{equation}$$ and, for $z \neq 0$, we can take $f$ to have the form $$\begin{equation}
f(x, y, z) = \begin{cases}
0 &\text{if } g(x, z) = h(y, z) \\
1 & \text{if } g(x, z) \neq h(y, z) \end{cases} \,.
\end{equation}$$ Now suppose we want $f$ to have the following values for $x, y \in \{0, 1\}$ and $z = 1$: $$\begin{eqnarray}
f(0, 0, 1) &=& 0 \,, \\
f(0, 1, 1) &=& 0 \,, \\
f(1, 0, 1) &=& 0 \,, \\
f(1, 1, 1) &=& 1 \,.
\end{eqnarray}$$ This doesn't work. The first three conditions would require $g(0, 1) = h(0, 1)$, $g(0, 1) = h(1, 1)$, and $g(1, 1) = h(0, 1)$, which together imply $g(1, 1) = h(1, 1)$, but the last value would require $g(1, 1) \neq h(1, 1)$.