Generate all sums of a subset in a range faster than O ((k + N) * 2 ^ (N / 2))?

Question

Is there a way to generate all sums of a subset s ₁ , s ₂ , ..., s _k that fall into the range [A, B] faster than O ((k + N) * 2 ^{N / 2} ), where k is the number amounts available in [A, B]? Note that k is known only after we have listed all the sums of the subsets inside [A, B].

I am currently using the modified Horowitz-Sahni algorithm. For example, I first call it for the smallest amount greater than or equal to A, which gives me s ₁ . Then I call it again for the next smallest amount greater than s ₁ , giving me s ₂ . Repeat this until we find the sum s _{k + 1} greater than B. There are many calculations repeated between each iteration, even without restoring the initial two 2 ^{N / 2} lists, so is there a way to do better?

In my problem, N is about 15, and the value of the numbers is of the order of millions, so I did not consider the dynamic programming route.

Answer 1

Check the subset sum on Wikipedia. As far as I know, this is the fastest algorithm that works in O (2 ^ (N / 2)) time.

Edit: If you are looking for several possible sums, not just 0, you can save the final arrays and just repeat them again (which is roughly equal to O (2 ^ (n / 2)) and save them recalculated. The value of all possible subsets does not change with the aim of.

Edit again: I'm not quite sure what you want. Do we search K for one independent value each, or are we looking for some subset that has a value in a certain range with a width of K? Or are you trying to zoom in on the second using the first?

Edit in response: Yes, you get a lot of duplicates without even rearranging the list. But if you do not rearrange the list, it is not O (k * N * 2 ^ (N / 2)). Building a list of O (N * 2 ^ (N / 2)).

If you know A and B right now, you can start iterating and then just not stop when you find the correct answer (lower bound), but keep going until it goes out of range. It should be about the same as solving the sum of the subset for just one solution, including only + k more operations, and when you are done, you can cut the list.

More rights: You have a range of sums from A to B. First, you solve the problem of the sum of the subset for A. Then you just continue the iteration and save the results until you find a solution for B, then stop. Now you have every sum between A and B in one run, and that will cost you only one problem with the sum of the sums plus the K operations for K values ​​ranging from A to B, which is linear and pleasant and fast.

s = *i + *j; if s > B then ++i; else if s < A then ++j; else { print s; ... what_goes_here? ... } 

No no no. Now I get the source of your confusion (I misunderstood something), but it is still not as complicated as what you originally had. If you want to find ALL combinations within a range, and not one, you just have to iterate over all combinations of both lists, which is not so bad.

Sorry for using auto. C ++ compiler 0x.

 std::vector<int> sums; std::vector<int> firstlist; std::vector<int> secondlist; // Fill in first/secondlist. std::sort(firstlist.begin(), firstlist.end()); std::sort(secondlist.begin(), secondlist.end()); auto firstit = firstlist.begin(); auto secondit = secondlist.begin(); // Since we want all in a range, rather than just the first, we need to check all combinations. Horowitz/Sahni is only designed to find one. for(; firstit != firstlist.end(); firstit++) { for(; secondit = secondlist.end(); secondit++) { int sum = *firstit + *secondit; if (sum > A && sum < B) sums.push_back(sum); } } 

This is not great yet. But it could be optimized if you knew in advance that N is very large, for example, matching or hashing sums using iterators, so that any given firstit can find suitable partners in secondit, reducing execution time.

Answer 2

This can be done in O (N * 2 ^ (N / 2)) using ideas like Horowitz Sahni, but we are trying to do some optimizations to reduce constants in BigOh.

We do the following

• Step 1 : Divide into N / 2 sets and generate all possible 2 ^ (N / 2) sets for each split. Name them S1 and S2. We can do this in O (2 ^ (N / 2)) (note: there is no N-factor due to the optimization we can do).

• Step 2 : Then collect more from S1 and S2 (say, S1) in O (N * 2 ^ (N / 2)) time (we optimize here without sorting both).

• Step 3 : Find the sums of the subset in the range [A, B] in S1 using a binary search (as you sort).

• Step 4 : Then, for each sum in S2, use the binary search to find the sets from S1, the combination of which gives a sum in the range [A, B]. This is O (N * 2 ^ (N / 2)). At the same time, find whether this corresponds to the corresponding set in S2 in the range [A, B]. The optimization here is to combine loops. Note. This gives a representation of the sets (in terms of two indices in S2), and not the sets themselves. If you want all sets, it will be O (K + N * 2 ^ (N / 2)), where K is the number of sets.

Further optimizations are possible, for example, when the sum from S2 is negative, we do not consider the sum <A, etc.

Since Steps 2,3,4 should be quite clear, I will talk in detail about how to take the first step in O (2 ^ (N / 2)) time.

For this we use the concept of Gray Codes . Gray codes are a sequence of binary bit patterns in which each pattern differs from the previous pattern with exactly one bit. Example: 00 -> 01 -> 11 -> 10 is a gray code with 2 bits.

There are gray codes that pass through all possible N / 2-bit numbers, and they can be generated iteratively (see the wiki page I linked to) O (1) times for each step (total O (2 ^ (N / 2))), given the previous bit pattern, that is, the specified current bit pattern, we can generate the next pattern bit O (1) times.

This allows us to form all the sums of the subset using the previous sum and changing it by simply adding or subtracting one number (corresponding to a different bit position) to get the next sum.

Answer 3

If you change the Horowitz-Sahni algorithm correctly, it will be slightly slower than the original Horowitz-Sahni. Recall that Horowitz-Sahni has two lists of subsets of sums: sums of subsets in the left half of the original list and sums of subsets in the right half. Call these two lists of sums L and R. To get the subsets that sum with some fixed value of A, you can sort R and then look for a number in R that matches each number in L using a binary search. However, the algorithm is asymmetric only to maintain a constant factor in space and time. It is a good idea for this problem to sort both L and R.

In my code below, I also cancel L. Then you can save two pointers in R, updated for each record in L: a pointer to the last record in R, which is too small, and a pointer to the first record in R, which is too high. When you move to the next entry in L, each pointer can either move forward or stay in place, but they will not have to move backward. Thus, the second stage of the Horowitz-Sahni algorithm takes only linear time in the data generated in the first stage, plus linear time in the output length. Until the constant factor, you cannot do better (after you have completed this “mid-visit” algorithm).

Here is the Python code with an example input:

 # Input terms = [29371, 108810, 124019, 267363, 298330, 368607, 438140, 453243, 515250, 575143, 695146, 840979, 868052, 999760] (A,B) = (500000,600000) # Subset iterator stolen from Sage def subsets(X): yield []; pairs = [] for x in X: pairs.append((2**len(pairs),x)) for w in xrange(2**(len(pairs)-1), 2**(len(pairs))): yield [x for m, x in pairs if m & w] # Modified Horowitz-Sahni with toolow and toohigh indices L = sorted([(sum(S),S) for S in subsets(terms[:len(terms)/2])]) R = sorted([(sum(S),S) for S in subsets(terms[len(terms)/2:])]) (toolow,toohigh) = (-1,0) for (Lsum,S) in reversed(L): while R[toolow+1][0] < A-Lsum and toolow < len(R)-1: toolow += 1 while R[toohigh][0] <= B-Lsum and toohigh < len(R): toohigh += 1 for n in xrange(toolow+1,toohigh): print '+'.join(map(str,S+R[n][1])),'=',sum(S+R[n][1]) 

---

Moron (I think he should change his username) raises the reasonable problem of optimizing the algorithm a bit, skipping one of them. In fact, since each list of L and R is a list of sizes of subsets, you can do combined generation and sort each of them in linear time! (T. E. Linear in list lengths.) L is the union of two lists of sums, those that include the first term, the term [0], and those that do not. Therefore, in fact, you should just make one of these halves in sorted form, add a constant and then merge the two sorted lists. If you apply this idea recursively, you save the logarithmic coefficient over time to make sorted L, i.e. The coefficient N in the original variable of the problem. This provides a good reason to sort both lists as they are created. If you sort only one list, you have several binary searches that can re-enter this coefficient N; at best, you need to optimize them somehow.

At first glance, the O (N) factor can still exist for another reason: if you want not only the sum of the subset, but also the subset that makes up the sum, then it looks like O (N) time and space for storing each subset in L and in R. However, there is a data exchange trick that also gets rid of this O (N) coefficient. The first step is to save each subset of the left or right half as a linked list of bits (1 if the term is included, 0 if it is not included). Then, when the list L is doubled in size, as in the previous paragraph, the two linked lists for the subset and its partner can be shared, except in the chapter:

  0 | v 1 -> 1 -> 0 -> ... 

Actually, this trick of the linked list is an artifact of the cost model and will never be really useful. Since in order to have pointers in RAM with a value of O (1), you need to define data words with bits O (log (memory)). But if you have data words of this size, you can store each word as a vector with one bit, and not with this pointer structure. Ie, if you need less than gigaword memory, you can save each subset in a 32-bit word. If you need more than gigaword, then you have 64-bit architecture or emulation of it (or maybe 48 bits), and you can still store each subset in one word. If you are correcting the RAM cost model to account for the size of a word, then this factor N has never been like that.

So, interestingly, the time complexity of the original Horowitz-Sahni algorithm is not equal to O (N * 2 ^ (N / 2)), it is O (2 ^ (N / 2)). Similarly, the time complexity of this problem is O (K + 2 ^ (N / 2)), where K is the output length.