I'm sure this problem must be well-known...
Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the difference of products $$ \Delta = \left|\left(\prod_{x\in B}x\right) - \left(\prod_{x\in A}x\right)\right| $$ is as small as possible.
If it helps, you can assume that all the members of $S$ are integers, and in fact you can assume that they are all prime! In my particular use-case, we're trying to split some big integer $n$ into its "squarest possible" pair of factors, and $S$ is simply a prime factorization of $n$ which we happen to have lying around.
What's the best way to do this? The brutish ways I have thought of are:
- Trial division (assuming everything is prime). Awful performance.
int PS = productOf(S);
for (int PA = sqrt(PS); PA >= 1; --PA) {
if (PS % PA == 0) {
int PB = PS / PA;
return { factorsOf(PA), factorsOf(PB) };
}
}
- Search all the possible partitions. Would give better performance, I think, because $\lvert S\rvert! \ll \prod{S}$, but still "obviously" a dumb algorithm.
int currentDiff = productOf(S);
intset currentA = {};
for (intset A in partitionsOf(S)) {
int PA = productOf(A);
int PB = productOf(S)/PA;
if (PB >= PA && PB-PA < currentDiff) {
currentA = A;
currentDiff = PB-PA;
}
}
return { currentA, S - currentA };
Is there any simple-ish algorithm to solve this problem without relying on brute exhaustive search?
I wonder if it would work to minimize the difference of sums $\sum_{x\in B}{\log{x}} - \sum_{x\in A}{\log{x}}$, and if that problem has a simpler known solution...
