For a problem with no extra assumptions or structure, an exhaustive search is probably best. A Tuples
based search has a memory complexity of $O(n_1n_2n_3\cdots)$ (or $O(n^k)$ if the $k$ sets are of about the same size $n$). A procedural-programming approach both is time-efficient and uses little memory; it is slightly faster than @Bill's on @b.gatessucks' example. Here is the basic idea:
Do[
val = f[x, y, z];
If[val > max, (* see below for initialization of max *)
max = val; args = {x, y, z}],
{x, setx}, {y, sety}, {z, setz}]
Vectorizing the inner loop, if the function f
supports it, is much faster than the above, especially as the size n
of the sets grows:
max = -Infinity;
Do[
vals = f[x, y, setz]; (* f must be listable *)
val = Max@vals;
If[val > max,
max = val;
args = {x, y, First@Pick[setz, vals, max]}],
{x, setx}, {y, sety}];
{max, args}
If f
is compilable and listable, then compiling this speeds things up a little bit more on @b.gatessucks' example.
The following gives some idea of what is possible:
Fig. 1.
The time of execution for three sets of size 3
, 6
,... 768
. Note the uncompiled, vectorized Do
loop is quite fast, with a time complexity that appears to be somewhat less than $O(n^3)$, unlike the others. It ought to be $O(n^2(1+\epsilon\,n))$, but I suppose $\epsilon\,n$ is still rather less than $1$ in the plot.
The MaximalBy
code is from my comment. The basis for the compiled and uncompiled procedural code is the first Do
loop above; the second Do
is the basis for the "vectorized" version. When compiled, one can make it Listable
and parallelized on one of the arguments; that's the fastest way I have.
I've been playing with it, obviously, trying to create an interface that automatically chooses the optimal method (and when not automatic, controlled by options). But I'm not done. It's hardly relevant to the question at hand, unless speed on moderately sized sets is important to the OP. I don't mind sharing the code, but I'm not sure it would be of broad interest.