2
$\begingroup$

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...

$\endgroup$
7
  • $\begingroup$ A quick note regarding your final point on minimising the difference of logs: the problem can be reduced to 2-partition (en.wikipedia.org/wiki/Partition_problem) which is NP-complete, but has a pseudo-polynomial dynamic programming solution (efficient in practice). $\endgroup$ – integrator Oct 19 '20 at 16:19
  • $\begingroup$ Here is relevant link to the problem you want to solve: cstheory.stackexchange.com/questions/16902/… $\endgroup$ – integrator Oct 19 '20 at 16:36
  • $\begingroup$ FWIW, that problem seems like "split S so that $\prod{A} = \prod{B}$ exactly," and I don't (yet) understand how to adjust the solution to merely minimize the difference $\prod{B}-\prod{A}$. $\endgroup$ – Quuxplusone Oct 19 '20 at 17:12
  • $\begingroup$ Are you looking for practical solutions or do you care about theoretical running time? If practical, what are the typical sizes of the sets and the numbers? $\endgroup$ – D.W. Oct 19 '20 at 18:22
  • $\begingroup$ @D.W.: I'm looking for practical solutions IRL, but I'm also morbidly curious about impractical ones and would not downvote them. My inputs are the-prime-factorizations-of consecutive integers starting at $n=2$, so my set sizes are $\Omega(n)$ for whatever that's worth. :) Circa $n=10^9$, my "trial division" algorithm becomes noticeably "slow." I have not yet implemented the "search all partitions" algorithm because I decided I'd better ask for better algorithms before I spend the time to implement another one. $\endgroup$ – Quuxplusone Oct 19 '20 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.