5
$\begingroup$

Given lists $A_1, A_2, \dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 \times A_2 \times \dots \times A_n$ ordered by the value $x_1 + x_2 + \dots + x_n$, where $x_i\in A_i$.

I can't simply create all combinations in memory and sort them because of large amount of data.

For example, I have 1000 drinks, 1000 main courses and 1000 desserts. I want to find the 100 cheapest meals but I can't store all 1,000,000,000 elements in memory.

Additional details

  1. I have Drinks, Main Courses and Desserts already sorted.
  2. I've found some solutions like Efficient sorted cartesian product of 2 sorted array of integers but only for 2 lists. For greater amount of sets it still memory-consuming.
  3. Lazy generating next "sorted" value will be useful.
  4. If no efficient exact algorithm, it could be heuristic or approximation algorithm.
  5. It's similar to X + Y sorting problem , efficient faster than O(n^2 * log n) solution is unknown

Question:

Are there an efficient ways to get only $k$ cheapest(*) elements of Cartesian product?
(*) Price of the result element is sum of all numbers in that element.

$\endgroup$
5
$\begingroup$

If $k$ is known in advance, we can do the following. I will assume that each list $A_j$ is sorted according to cost. What we will do is a weighted form of breadth-first exploration of index tuples $(i_1,\dots,i_n)$, storing the current candidates in a (bounded length) priority queue $Q$ according to their cost $A_1[i_1]+\dots+A_n[i_n]$. Initially $Q$ contains just the initial tuple $(0,\dots,0)$.

In each iteration, pop the first tuple $t=(i_1,\dots,i_n)$ off $Q$; this is a cheapest previously unexplored solution. Then generate its successors of the form $t^{(j)}=(i_1,\dots,i_j+1,\dots,i_n)$, compute their cost, and insert them into $Q$ accordingly.

We can avoid creating duplicates by only creating the successors $t^{(j)}$ up to the first index $j$ for which $i_j>0$; e.g. for $t=(0,1,0,2)$ we would only create $(1,1,0,2)$ and $(0,2,0,2)$ (the other tuples $(0,1,1,2)$ and $(0,1,0,3)$ instead get created as successors of $(0,0,1,2)$ and $(0,0,0,3)$, respectively). This eliminates the need for a closed list of explored tuples. We still need to store the priority queue $Q$, but it can be bounded to length $k-j$, where $j$ is the current iteration, with any entries beyond that discarded.

For example, suppose we have $A_1=(1,5,7),A_2=(1,2,5),A_3=(1,3,4)$, and $k=4$.

  • Initially, $Q=[(0,0,0)]$.
  • Pop $(0,0,0)$, with cost $3$, and push $(1,0,0),(0,1,0),(0,0,1)$. Their costs are $7,4,5$, respectively, and $Q$ is now $[(0,1,0),(0,0,1),(1,0,0)]$.
  • Pop $(0,1,0)$ (cost $4$), and push $(1,1,0)$ (cost $8$) and $(0,2,0)$ (cost $7$). $Q$ is now $[(0,0,1),(1,0,0),(0,2,0),(1,1,0)]$; since we only need two more solutions, we can drop the last two, getting $[(0,0,1),(1,0,0)]$.
  • Pop $(0,0,1)$ (cost $5$), and push $(1,0,1)$ (cost $9$), $(0,1,1)$ (cost $6$), and $(0,0,2)$ (cost $6$). $Q$ is now $[(0,1,1),(0,0,2),(1,0,0),(1,0,1)]$; again, we can drop unneeded entries since we only want one more, getting $[(0,1,1)]$.
  • Pop $(0,1,1)$; done.

To see that this method is correct, we just need to prove the following:

  1. Given the above restrictions, any index tuple $i=(i_1,\dots,i_k)$ (with $0\le i_j\le size(A_j)$) is reachable along the unique path $(0,\dots,0)\to\dots\to(0,\dots,0,i_k)\to\dots\to(0,\dots,0,i_{k-1},i_k)\to\dots\to i$.
  2. The cost of the tuples along that path is nondecreasing, since the weights are nonnegative.
  3. If there is another tuple $i'$ with a higher cost, and $i'$ is popped off $Q$ during the algorithm, then so are all tuples along the path to $i$ (using induction).
  4. If a tuple $i'$ is discarded due to the length restriction, then there are at least $k$ tuples whose cost is no greater than that of $i'$.
$\endgroup$
  • $\begingroup$ Nice. It may be useful to provide the core reason (inductive step) for correctness, though. One might think that one had to go from $t$ to $(1,\dots, 1, i_j + 1, 1, \dots, 1)$ because that's clearly cheaper than $t^{(j)}$. $\endgroup$ – Raphael Sep 7 '15 at 22:54
  • $\begingroup$ @Raphael What do you mean "from $t$ to $(1,…,1,i_j+1,1,…,1)$" ? $\endgroup$ – Dmitry Yaremenko Sep 8 '15 at 8:50
  • $\begingroup$ @DmitryYaremenko That one would have to add those tuples to $Q$. $\endgroup$ – Raphael Sep 8 '15 at 12:15
2
$\begingroup$

This is more of a median problem, so compared to sorting you may be able to shave some work off for large k (for small k, expanding from the origin is probably best).

Assuming all sets are sorted, the function $s(x) = \sum{}{x_i}$ has nonnegative partial derivative in all dimensions, so if you pick a random pivot $p$ such that $0 < p <= \sum{max(A_i)}$ then the boundary of $P(p) = \{y: s(y) <= p \}$ has dimension $n-1$ and can be traced in that time (ie if $|A_i| = a$ and there are $a^n$ tuples, you only have to evaluate $o(a^{n-1})$ points to count the volume of $P(p)$). During tracing it's a simple matter to keep a running count of $|P|$.

If you binary search on $p$ then I believe you have $o(a^{n-1}\log{a})$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.