Splitting lists of numbers in polynomial time s.t. the products are similar

Question

I have a list of natural numbers L=(n1,n2,...,nk)

I want to split this list into 2 lists L1, and L2, such that the product of the elements in the lists is similar.

So the product(L1) of a list L1=(l1,...,lx) is l1*l2*...*lx. I want to minimize abs(product(L1)-product(L2)).

Is there any way to this with a polynomial algorithm?

I would further be interested in a generalized form, splitting the original list into k parts, all as equal as possible.

I think that this may be related to the subset sum problem, which is NP. Thank you all in advance.

Answer 1

To analyze this, take the logs of the products of your two subsets' elements (log(l1*l2*...*lx) = log(l1)+log(l2)+...+log(lx)). Because you need to assign all of your numbers, the best subset assignment will simply be the one where the sums of the two products' logs are as close as possible.

The partition problem is a special case of this problem, and since that problem is NP-complete, your problem is as well.

That being said, you might still be able to solve this problem reasonably efficiently using integer optimization. Assign binary variable x_i to each number i; all values 1 are assigned to one set and all values 0 are assigned to the other. Then you have the following optimization problem:

In this model, 2x_i-1 adds the log(l_i) value if x_i=1 and subtracts if x_i=0, and the pair of constraints forces a to be greater than or equal to the absolute value of the differences in summed logs.

Since SO is a website primarily focused on programming challenges, I'll drop in some R code that solves this optimization problem using the lpSolve package. There are many free and non-free options for optimization software.

library(lpSolve)
minProd <- function(vals) {
  # Setup and solve optimization problem
  c1 <- c(-2*log(vals), 1)
  rhs1 <- -sum(log(vals))
  c2 <- c(2*log(vals), 1)
  rhs2 <- sum(log(vals))
  obj <- c(rep(0, length(vals)), 1)
  res <- lp("min", obj, rbind(c1, c2), ">=", c(rhs1, rhs2),
            binary.vec=seq(length(vals)))

  # Output solution
  s0 <- vals[res$solution[seq(length(vals))] < 0.001]
  s1 <- vals[res$solution[seq(length(vals))] > 0.999]
  print(paste(paste(s0, collapse="*"), "=", prod(s0)))
  print(paste(paste(s1, collapse="*"), "=", prod(s1)))
}
minProd(c(2, 3, 6))
# [1] "6 = 6"
# [1] "2*3 = 6"
minProd(c(2, 3, 4, 5, 6, 7, 8, 9, 10))
# [1] "4*6*8*10 = 1920"
# [1] "2*3*5*7*9 = 1890"