How can I find the k-th largest element in an exponentially large list?

Suppose there are n sets of real numbers: S[1], S[2], ..., S[n]. We know two things about these sets:

  1. Each set S[i] has exactly 3 elements.

  2. All elements in each of the sets S[i] are real numbers in the [0, 1] range. (I don’t know if this detail can be helpful for the solution, though).

Let’s consider a set T of all numbers that can be represented as p[1] * p[2] * p[3] * ... * p[n] where p[i] is an element of S[i]. This set T, obviously, has 3^n elements.

My question is, given the sets S[1], S[2], ..., S[n] (1 <= n <= 30) and some 1 <= k <= 10 as input, can we find the k-th largest number in T faster than in O(3^n) time? It’s important that I need not only the k-th largest number, but also the corresponding numbers (p[1], p[2], p[3], ... , p[n]) that produce it.

Even if the answer is no, I would appreciate any hints on how you would solve this problem approximately, maybe, by using some heuristics? I know about beam search, but maybe you could suggest something else? And even for beam search, it is not really clear how to implement it here the best way.

If the exact answer can be obtained algorithmically in less than O(3^n) time, I would greatly appreciate it if you could point out the solution.

Answer

Well, you know that the largest product is the one that uses the largest factor from each set.

Furthermore, every other product can be formed by starting with a larger one, and then decreasing the factor chosen in exactly one set.

That leads to a simple search:

  1. Put the largest product in a max-first priority queue.

  2. Repeat k times:

    a. Remove the largest product p from the priority queue

    b. For each set that has a smaller number than the one selected in p,
    generate the product formed by decreasing that number to the next lower one in that set. If this selection of factors hasn’t been seen before, then add it to the priority queue.

Products will be removed from the queue in decreasing order, so the kth one you take out is the kth largest.

Complexity is about N*(k log kN), depending on how you implement things.

Note that there may be multiple ways to select the factors that produce the same product. This solution considers those ways to be distinct products, i.e., each way is counted when finding the kth largest. That may or may not be what you want.