Databases
StackOverflow2013
Postsdbo
POFind the (100) highest sums out of elements from multiple lists
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFind the (100) highest sums out of elements from multiple lists
    primarykey
    data
    text
    <p>I have the following problem (in my version there are some constraints which probably make the problem easier to solve, but a general solution would also be nice):</p> <p>I have 4 lists, with 10 entries. The first list contains integer entries between 0 and 6, the other three contain entries between 0 and 3. I now have to find the 100 best combinations of elements of these four lists. One combination consists of the sum of 4 values, one from each list. Note that I don't only need to know the values of the resulting elements, but also how they were composed, as there is more information associated with the values. </p> <p><strong>Example 1:</strong></p> <pre><code>list A: 6, 3, 2, 2, 1, 0, 0, 0, 0 list B: 3, 2, 0, 0, 0, 0, 0, 0, 0 list C: 2, 2, 0, 0, 0, 0, 0, 0, 0 list D: 3, 1, 1, 1, 1, 1, 0, 0, 0 </code></pre> <p>The five best combinations would in this case be:</p> <ul> <li>14 (A[0] + B[0] + C[0] + D[0])</li> <li>14 (A[0] + B[0] + C[1] + D[0])</li> <li>13 (A[0] + B[1] + C[0] + D[0])</li> <li>13 (A[0] + B[1] + C[1] + D[0])</li> <li>12 (A[0] + B[0] + C[0] + D[1])</li> </ul> <p>Note that I have sorted the entries of the lists, as this would probably the first step of most algorithms which solve this problem. </p> <h2>Trivial solution</h2> <p>The easiest solution consists of forming all 10.000 possible combinations and then choose the hundred bests out of these. One does not even have to sort the 10.000 possible combinations. One can first scan through the array and analyze which value appears how often. Then one can pick the hundred best values (and their further attributes) in the next scan through the values. </p> <h2>A solution which does not work</h2> <p>Another idea which came to my mind is the following: First one has to sort the lists. In each list I want to find an index, which separates those entries which can contribute to a solution from them which can't. When one had to find the four best combinations in example 1, one could for example select the first two elements of lists <code>B</code> and <code>C</code>, and the first one of lists <code>A</code> and <code>D</code> This would yield:</p> <pre><code>A: 6 B: 3, 2 C: 3, 2 D: 3 </code></pre> <p>All combinations of these sublists would yield the optimal solution. However this is not always possible, as can be seen in the following example:</p> <p><strong>Example 2:</strong></p> <p>(this time with only two lists)</p> <pre><code>list A: 6, 5, 5, 0, 0, ... list B: 3, 1, 1, 0, 0, ... </code></pre> <p>Here, the best four solutions are </p> <ul> <li>6 + 3</li> <li>5 + 3</li> <li>5 + 3</li> <li>6 + 1</li> </ul> <p>However this solution can not be found with indexes, which separate four combinations from all other combinations. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMisch
    1. USMisch
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFind the (100) highest sums out of elements from multiple lists
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFind the (100) highest sums out of elements from multiple lists
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFind the (100) highest sums out of elements from multiple lists
      1. This table or related slice is empty.
      1. VTUpMod
    1. COOne approach to solve this (in general) is to build a heap where the nodes store (1) an index for each list, (2) the list that was last incremented. The children have one index incremented, which is at least the (2) value (so we can't increment B then A). When the values are all small, you can probably get away with counting the groups that sum to (e.g.) 15, 14, 13, etc.
      singulars
      1. POFind the (100) highest sums out of elements from multiple lists
      1. USNabb
    2. COI would've suggested Evgeny Kluev's answer but I think you can do this in O(n) using a dynamic programming approach. You can google the solution to it. (e.g. dynamic programming largest sum of elements of array -- or something like that)
      singulars
      1. POFind the (100) highest sums out of elements from multiple lists
      1. This table or related slice is empty.
    3. CO@PotatoQueue - my answer gives a solution using dynamic programming (at least that is the category of it as I remember from university). It is O(N), where N is the total number of values in the 4 lists.
      singulars
      1. POFind the (100) highest sums out of elements from multiple lists
      1. USKnaģis
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload