Is it possible to iteratively get the partial sums of an array in descending order?

user_824501 0
Viewed 105

We have a sorted array, say

30, 20, 10, -1, -2, -15

Now we want to calculate its partial sums (for each number, you can choose to add it or not add it), and fetch top n largest numbers of them (say, top 11 of them) in the descending order, i.e.

60 = 30 + 20 + 10
59 = 30 + 20 + 10 -1
58 = 30 + 20 + 10    -2
57 = 30 + 20 + 10 -1 -2
50 = 30 + 20
49 = 30 + 20      -1
48 = 30 + 20         -2
47 = 30 + 20      -1 -2
45 = 30 + 20 + 10       -15
44 = 30 + 20 + 10 -1    -15
43 = 30 + 20 + 10    -2 -15

A naive solution is to calculate all the combinations (for the example above, there are 2^6 = 64 combinations), sort them in the descending order, and then fetch the first 11 numbers of them:

60, 59, 58, 57, 50, 49, 48, 47, 45, 44, 43, 42, 40, 39, 38, 37, 35, 34, 33, 32, 30, 30, 29, 29, 28, 28, 27, 27, 25, 24, 23, 22, 20, 19, 18, 17, 15, 15, 14, 14, 13, 13, 12, 12, 10, 9, 8, 7, 5, 4, 3, 2, 0, -1, -2, -3, -5, -6, -7, -8, -15, -16, -17, -18

However, when the length of the array is large, calculating all the combinations is unfeasible. So the question is, is it possible to fetch the top n largest partial sums in an iterative manner, e.g. fetch one number at a time?

EDIT

To be clear, the end goal is, assuming the array to be global, I want a function f(): by calling f() iteratively, it returns the largest partial sums in the descending order

Call f(), return 60
Call f() again, return 59
Call f() again, return 58
......

sorting algorithm
1 Answers

There is a very general procedure for this sort of problem called Lawler-Murty described at http://www.vldb.org/pvldb/vol4/p1028-golenberg.pdf. It is most practical when you don't want all of the answers, perhaps just the top 10, or enough to exhaust the patience of a human looking through search results.

Here is an attempt to provide a simpler version specific to your problem.

Think of each answer as defined by a vector of bits, where 0 means take the lower option and 1 means take the higher option. That is: if the number is positive then 1 means chosen and 0 not chosen. If it's negative, then 1 means not chosen and 0 means chosen. So 111111 means 30+20+10 (+0+0+0) and 000000 means (0+0+0)-1-2-15. 111111 will always be the highest answer.

Think of these vectors as arranged in a tree, with 111111 at the top. You can find the parent of any vector with any 0 bits by setting the leftmost 0 bit. This means that the parent always has a higher value than its children. Nodes have a variable number of children, with 111111 having the most: 011111, 101111, 110111, 111011, 111101, and 111110. One way to enumerate all of the children of a parent is to take all of the 1s in the parent which do not have a 0 bit to their left and clear them in turn.

The top of the tree is 111111. Put this in a priority queue ordered by the sum computed from each vector. Now repeatedly take the item out of the queue with highest sum, print it out, and put all of its children in the queue.

This prints out all of the answers in non-increasing order of sum. The children of a maximum value are no higher than the parent, so the maximum value in the priority queue never increases. Every possible answer has a chain of parents leading back up to 111111 (set the leftmost bit) so you find every possible answer.

user_2404570
Related