Tag: Algorithms

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_{xin B}xright) – left(prod_{xin A}xright)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 Srvert! 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_{xin B}{log{x}} – sum_{xin A}{log{x}}$, and if that problem has a simpler known solution…