Compute a commutative and associative operation on n-2 arguments efficiently

Question

Considering a function $f$ such that: $$ f(x_1, x_2, x_3) = f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3)) $$ and $$ f(x_1, x_2) = f(x_2, x_1) $$

and a set $X = \{ x_1, \dots, x_n \}$; how to compute $$f(x_1, \dots, x_{i - 1}, x_{i + 1}, \dots, x_{j-1}, x_{j+1}, \dots, x_n)$$ for all pairs $i, j \in 1, \dots, n$, $i < j$ while minimizing the number of calls to $f$?

• Only $f(x)$ and $f(x, y)$ can be computed
• $f^{-1}$ is not defined

---

For example, let $f$ be addition, i.e, $f(x_1, x_2, \cdots, x_n)=x_1+x_2+\cdots+x_n$. However, only calls to $f$ with one or two arguments are allowed, i.e $f(x)=x$ and $f(x_1,x_2)=x_1+x_2$. In particular, neither subtraction nor negation is allowed. The problem is to compute all sums of $n-2$ numbers among the given $n$ numbers with the least number of additions. There are $n(n-1)/2$ such sums.

Answer 1

(1) You can compute $f(x_1,\dots,x_{i-1})$ for all $i$ with $n-2$ calls to $f$. (Simply iterate over $i:=1,\dots,n$.)

(2) Then, using (1), you can compute $f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1})$ for all $i,j$ with $n(n-1)/2$ more calls to $f$. (For each $i$, iterate over $j:=i+2,\dots,n$.)

(3) You can also compute $f(x_{j+1},\dots,x_n)$ for all $j$ with another $n-2$ calls to $f$. (Iterate over $j:=n,\dots,1$.)

(4) Finally, using (2) and (3), you can compute $f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1},x_{j+1},\dots,x_n)$ for all $i,j$ with another $n(n-1)/2$ calls to $f$.

In all, this uses about $n^2+n$ calls to $f$.

This is within a factor of 2 of the best possible, as you need to output $n(n-1)/2$ different values, so obviously you'll need to make at least $n(n-1)/2$ calls to $f$.

Answer 2

(Motivation: let $h = n/2$.
Given $f_{ih} = f(x_i\dots x_{h-1}) \text{ and } f_{hj} = f(x_h\dots x_j)$ (precomputed in about $n$ evaluations of $f$),
$f(x_{i+1}\dots x_{j-1})$ can be computed as $f(f_{(i+1)h}, f_{h(j-1)})$ for all $i\lt h\lt j$.
This saves ?$\frac{(n-2)(n-3)} 2 - n$? evaluations.
Similarly for $q = n/4, 3q = h+q, o = n/8, 3o = q+o, 5o = h+o, 7o = 3q+o, \dots$.)

---

The above promises to be a bookkeeping headache.
Instead, pre-compute $f(x_{k2^l}\dots x_{(k+1)2^l-1}), 0<l\le\lg_2(n), 0<k<\frac n {2^l}$ in about n evaluations of $f$:
Any $f_{ij}$ can be computed in less than $2\lg_2(n)$ evaluations.

An example

Let $f_{\boxed {lk}} := f(x_{k2^l}\dots x_{(k+1)2^l-1})$

Suppose $n = 13$, then $\lg_2(n) \approx 3.7$. Since $l$ is an integer and $0 < l \leq 3.7...$), this means $l$ iterates through $1, 2, 3$.

$l = 1,\quad 2^l = 2$

$0 < k < \frac n {2^l} = \frac {13} 2 = 6.5$

So $k$ iterates from $1$ to $6$ inclusive

$$ k=1,\quad f_{\boxed {11}} = f(x_2, x_3)\\ k=2,\quad f_{\boxed {12}} = f(x_4, x_5)\\ k=3,\quad f_{\boxed {13}} = f(x_6, x_7)\\ k=4,\quad f_{\boxed {14}} = f(x_8, x_9)\\ k=5,\quad f_{\boxed {15}} = f(x_{10}, x_{11})\\ k=6,\quad f_{\boxed {16}} = f(x_{12}, x_{13})\\ $$

$l = 2,\quad 2^l = 4$

$0 < k < \frac n {2^l} = \frac {13} 4 = 3.25$

So $k$ iterates from $1$ to $3$ inclusive

$$ k=1,\quad f_{\boxed {21}} = f(x_4 \dots x_7)\\ k=2,\quad f_{\boxed {22}} = f(x_8 \dots x_{11})\\ k=3,\quad f_{\boxed {23}} = f(x_{12} \dots x_{15})\\ $$

$l = 3,\quad 2^l = 8$

$0 < k < \frac n {2^l} = \frac {13} 8 = 1.625$

So $k$ iterates from $1$ to $1$

$$k=1,\quad f_{\boxed {31}} = f(x_8 \dots x_{15})$$

Answer 3

Count how many times each $x_i$ occurs in the argument list.

Suppose $X_1$ is the set of $x_i$ that occur once, $X_2$ is the set of $x_i$ that occur twice, ..., $X_m$ is the set of $x_i$ that occur $m$ times, ... etc.

Suppose $y \in X_j$, eventually you will have to evaluate $f(y)$ $j$ times. So instead of computing $f(y)$ $j$ times, just compute it once and save the result (in a dictionary, map, w/e).

Suppose $X_j = \{a, b, c\}$. You will have to evaluate $f(a, b, c)$ $j$ times. Instead of computing it $j$ times, evaluate it once and save the result.

Suppose $d \in X_{2^p}$ for some integer $p$. Let

• $d_0 := f(d)$
• $d_1 := f(d, d) = f(f(d), f(d)) = f(d_1, d_1)$
• $d_2 := f(d, d, d, d) = f(f(d, d), f(d, d)) = f(d_1, d_1)$
• ...
• $d_p := f(\underbrace{d, d, ..., d}_{2^p\ \text{times}}) = f(d_{p-1}, d_{p-1})$