I have a set $E$ which is the set of all possible $d$-tuples ($d$-dimensional vectors) of integers between $1$ and $n$.
Typically $d=3$ and $n\approx1000$, but for the sake of making a small example, suppose $d = 2$ and $n = 4$, so
$$E = \{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)\}\,.$$
Given an arbitrary nonempty $J\subseteq E$, I would like to find the product of the lengths of its projections on the axes, in other words, the area of the minimal axis-aligned bounding box of the 2d points in $J$.
For example, given $J = \{(2,3),(3,2),(4,1),(4,2)\}$, my function would return
$$f(J) = (\max(2,3,4,4)-\min(2,3,4,4))(\max(3,2,1,2)-\min(3,2,1,2)) = (4 - 2)(3 - 1) = 4\,.$$
I want to perform this calculation for every possible non-empty $J\subseteq E$, of which there are $2^{16} - 1 = 65,535$. At present I call built-in "Max" and "Min" commands every time, i.e. four such calls for each evaluation of $f$, hence $65,535\times 4 = 262,140$ calls. Presumably each time Max or Min is called, it sorts the positive integers fed to it.
This seems horribly inefficient, since for $J_1$ and $J_2$ having many elements in common, the lists to be sorted for $J_1$ are very similar to the lists to be sorted for $J_2$, so there may be great repetition of comparisons, even if the built in Max or Min function is efficient within itself.
What is a good way to solve this problem which achieves a balance between efficiency of time and memory, given the typical parameters $d = 3$ and $n = 1000$?
Should I store the nonempty subsets $J$ of $E$ in some kind of graph structure, and have my algorithm traverse this graph somehow?
EDIT:
So what I’m actually trying to do is to evaluate
$ R(s_1, \ldots, s_d, n_1, \ldots, n_d; q) = 1 + \sum_{J \in \mathcal{P}(E) \setminus \emptyset} (-1)^{|J|} \prod_{J' \in \mathcal{P}(J) \setminus \emptyset} \exp \left [ (-1)^{|J'|} \ln \left ( \frac{1}{q} \right ) \prod_{r=1}^d \max \left ( 0, s_r - \left ( \max_{e \in J'} e_r - \min_{e \in J'} e_r \right ) \right ) \right ], $
where $d \in \mathbb{N}$, $n_1, \ldots, n_d \in \mathbb{N}$, and $s_1, \ldots s_d \in \mathbb{N}$ with $1 \leq s_r \leq n_r$ for all $r \in \{1, \ldots, d\}$, and $E = \prod_{r=1}^d \{1, \ldots, n_r - s_r + 1 \}$, and $q$ is a symbol. This expression gives a polynomial in $q$. The sequence of coefficients of the polynomial is what I would like to obtain.
This formula itself might well not be a very good formula for computing this polynomial, but my present task is to make an algorithm based upon the formula.
The quantity
$ \prod_{r=1}^d \max \left ( 0, s_r - \left ( \max_{e \in J'} e_r - \min_{e \in J'} e_r \right ) \right ) $
represents the volume of the intersection of several contiguous subarrays of dimensions $s_1 \times \ldots \times s_d$, within a large array of dimensions $n_1 \times \ldots \times n_d$. The reason for taking the maximum of 0 and $s_r - \left ( \max_{e \in J'} e_r - \min_{e \in J'} e_r \right )$ is that some such intersections will be empty.
Re. Tom’s comment about enumerating bounding boxes instead of subsets, I did have the following idea, which I think might be in that spirit:
Since the volume of the intersection of several contiguous subarrays is invariant with respect to translation of that set of subarrays within the large array, I could choose only to compute the volumes of a certain number $M$ of representative cases, and then copy the result to all the translates. I think
$ M= 2^ { \left ( \prod_{r=1}^d \min(s_r, n_r – s_r + 1) \right ) -1 } $,
which I computed by supposing that the “top left” contiguous subarray was included in the set of subarrays, and asking which other contiguous subarrays could intersect that one.
EDIT:
I do apologise. In my original question, $f(J)$ should not be the product of the lengths of the projections of the subset on the axes, it should simply be the sequence of lengths of the projections on the axes. As can be seen in my first edit, above, I do not compute the product of those lengths $l_r$, rather, the product $\prod_{r=1}^d \max(0,(s_r - l_r))$. When the $n_r$ are large compared with the $s_r$, many of those products $\prod_{r=1}^d \max(0,(s_r - l_r))$ will be zero, which should allow me to check many fewer than the $2^{(1000^3)}$ cases mentioned in Tom's comment.
