# Sorting algorithm question **URL:** \ **Category:** Factual Questions\ **Created:** [September 8, 2007, 5:23am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443 "2007-09-08T05:23:04Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Polerius](https://avatars.discourse-cdn.com/v4/letter/p/d78d45/32.png) [@Polerius](https://boards.straightdope.com/u/Polerius)\ **Post date:** [September 8, 2007, 5:23am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/1 "2007-09-08T05:23:04Z")
Suppose you have a sequence of positive numbers, denoted by x\_k, k = 1 to N Without loss of generality, we can assume that the x\_k are sorted from smallest to largest. I want to sort sum x\_k, where k belongs to a subset of {1,…,N} over all subsets of {1,…,N} For example, if we sort the sums we could get ```auto x_1, x_2, x_3, x_1+x_2, x_4, x_5 ... ``` or ```auto x_1, x_2, x_1+x_2, x_3, x_4, x_1+x_2+x_3 ... ``` or some other sequence, depending on the relative values of the x\_k This seems like a generic enough problem that there is an algorithm to handle it. Is there one? Or, can you guys think of a numerically efficient way of doing it? ---
**Author:** ![4.66](https://avatars.discourse-cdn.com/v4/letter/4/2bfe46/32.png) [@4.66](https://boards.straightdope.com/u/4.66)\ **Post date:** [September 8, 2007, 9:48am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/2 "2007-09-08T09:48:25Z")
When you’re given a bunch of random numbers that need to be sorted finding a sorting algorithm can be complex. But when you’re building the list the list of numbers yourself, all you need to do is make sure the list is ordered at each step of your program. If, as your examples somewhat suggest, _x1+x2+x3_ is a valid sum, but _x1+x3_ (skipping the _x2_) is not, the problem isn’t all that hard. What you need to do is make a copy of the list, which is assumed to be ordered, and start inserting _x1+x2_ (and then _x1+x2+x3_, etc) at the right place. Any insert shouldn’t take any longer than _2n_ (the lists maximal length) steps, and with _n_ inserts this is a O(n^2) solution. On the other hand, if you need to take into account sums like _x1+x3_ the problem becomes harder. This is not because of the sorting requirement but because it seems like you need to generate all possible combinations of _x_’s. Each _xi_ can either be in or out, so you get _2^n_ possible combinations. The thing to note, however, is that it’s unlikely that there’ll also be _2^n_ different outcomes. As an example, consider the inputlist consisting of just _n_ copies of the number one. The outcome list will just be [_0,1,2,3,…,n_]. That’s something to take advantage of. Make sure your insert procedure handles duplicates correctly… Here’s your algorithm: [ul] [li] Start out with a result list consisting of just the number 0.[/li][li] To each result in the result list add x1 and insert it into the result list, which is now [_0,x1_][/li][li] To each result in the result list add x2 and insert it into the result list, which is now [_0,x1, x2, x1+x2_][/li][li] To each result in the result list add x3 and insert it into the result list, which is now [_0,x1, x2, x3, x1+x2, x1+x3, x2+x3, x1+x2+x3_] (Note that i haven’t ordered anything, nor removed duplicates. Your program _should_ do both these things)[/li][li] …[/li][/ul] (note that at each step the list of results doubles in length, so if there aren’t any duplicates you’ll end up with a list consisting of _2^n_ entries, as expected) If there are _m_ possible outcomes, you’ve now made _n_ steps that consist of at most _m_ inserts into a list of length _m_, which makes the algorithm O(_n_\*_m_^2). ---
**Author:** ![Quartz](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/quartz/32/267_2.png) [@Quartz](https://boards.straightdope.com/u/Quartz)\ **Post date:** [September 8, 2007, 10:37am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/3 "2007-09-08T10:37:04Z")
Can you clarify the problem a little? You’re starting with a pre-sorted array x[k] where k=1…N. Right? You’re trying to generate an array y where y[l]= Sum (x[a],x\*\*) and 1\<=a \ **Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [September 8, 2007, 11:20am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/4 "2007-09-08T11:20:24Z") If the second array, _y_[_k_] consists of all possible sums of the items in the _x_[_k_] array, the length of the _y_[_k_] array is 2[sup]k[/sup], i.e.: _x_[_k_] : 1, 2, 3, 4 _y_[_k_]: 0 (none of the items in _x_, optionally ignorable) 1 (_x_[1]) 2 (_x_[2]) 3 (_x_[1] + _x_[2]) 3 (_x_[3]) 4 (_x_[4]) 4 (_x_[1] + _x_[3]) 5 (_x_[1] + _x_[4]) 5 (_x_[2] + _x_[3]) 6 (_x_[1] + _x_[2] + _x_[3]) 6 (_x_[2] + _x_[4]) 7 (_x_[1] + _x_[2] + _x_[4]) 7 (_x_[3] + _x_[4]) 8 (_x_[1] + _x_[3] + _x_[4]) 9 (_x_[2] + _x_[3] + _x_[4]) 10 (_x_[1] + _x_[2] + _x_[3] +_x_[4]) You could eliminate duplicated sums, I guess, but even so, an _x_-array of any real size is going to make your _y_-array huge. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 8, 2007, 2:53pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/5 "2007-09-08T14:53:01Z")
One thing you should be aware of is that deciding whether there’s a subset of a given set S whose elements sum to k is NP-complete (in short, you’re not going to find an efficient solution). That really constrains any attempts at a clever solution. ---
**Author:** ![Rysto](https://avatars.discourse-cdn.com/v4/letter/r/ecccb3/32.png) [@Rysto](https://boards.straightdope.com/u/Rysto)\ **Post date:** [September 8, 2007, 6:11pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/6 "2007-09-08T18:11:20Z")
[QUOTE=4.66] When you’re given a bunch of random numbers that need to be sorted finding a sorting algorithm can be complex. But when you’re building the list the list of numbers yourself, all you need to do is make sure the list is ordered at each step of your program. If, as your examples somewhat suggest, _x1+x2+x3_ is a valid sum, but _x1+x3_ (skipping the _x2_) is not, the problem isn’t all that hard. What you need to do is make a copy of the list, which is assumed to be ordered, and start inserting _x1+x2_ (and then _x1+x2+x3_, etc) at the right place. Any insert shouldn’t take any longer than _2n_ (the lists maximal length) steps, and with _n_ inserts this is a O(n^2) solution. [/QUOTE] Am I missing something here? Why not construct a list with every sum and every number(takes 2n time) and then sort the list with a O(n log n) algorithm? If we must do something similar to your solution, use a self-balancing binary tree to hold the list, and then the run-time is still O(n log n). Of course, this is just applying my suggestion above to the binary tree sort algorithm. ---
**Author:** ![Polerius](https://avatars.discourse-cdn.com/v4/letter/p/d78d45/32.png) [@Polerius](https://boards.straightdope.com/u/Polerius)\ **Post date:** [September 8, 2007, 8:31pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/7 "2007-09-08T20:31:54Z")
[QUOTE=Bryan Ekers] If the second array, _y_[_k_] consists of all possible sums of the items in the _x_[_k_] array, the length of the _y_[_k_] array is 2[sup]k[/sup], i.e.: … You could eliminate duplicated sums, I guess, but even so, an _x_-array of any real size is going to make your _y_-array huge. [/QUOTE] Agreed. One thing I should clarify is that N is on the order of 10,000, so constructing y[k] is out of the question. I am interested in an algorithm that comes up with the first M elements of y[k], where M will be on the order of 100 to 1,000. Maybe, as **ultrafilter** mentions, this is not an easy problem to solve. The first two entries are easy to come up with x[1] x[2] The third entry is either x[3] or x[1]+x[2] if the third entry is x[3], the fourth entry is x[4] or x[1]+x[2] if the third entry is x[1]+x[2], the fourth entry is x[3] … etc The problem is that this gets quite complex very quickly, and I don’t see an easy way of extending it to obtain later elements of y[k]. I though this problem may be a variation of a well-known problem, for which an algorithm exists, and which I could adapt for my case. ---
**Author:** ![Polerius](https://avatars.discourse-cdn.com/v4/letter/p/d78d45/32.png) [@Polerius](https://boards.straightdope.com/u/Polerius)\ **Post date:** [September 8, 2007, 8:39pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/8 "2007-09-08T20:39:13Z")
[QUOTE=Polerius] One thing I should clarify is that N is on the order of 10,000, so constructing y[k] is out of the question. I am interested in an algorithm that comes up with the first M elements of y[k], where M will be on the order of 100 to 1,000. [/QUOTE] I guess that, since I only want the first M elements of y[k], I will only be interested in the first M elements of x[k], since x[M+1] will never be in any of the first M sums, since we already know M elements smaller than it. So, the problem reduces to finding the first M elements of y[k] using the first M elements of x[k]. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [September 8, 2007, 9:05pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/9 "2007-09-08T21:05:08Z")
If you only want the first M elements of Y, there might be a reasonable approach. Stick the elements of X into Y, and then generate all the two-value sums, and all the three-value sums, and so on and so forth. At some point the smallest possible sum of k elements (x[1] + … + x[k]) will be larger than the largest value in Y, so you can stop then. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 8, 2007, 9:08pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/10 "2007-09-08T21:08:23Z")
Could you clarify the thing asked above, about whether, say, x1 + x3 is a valid sum? If you only care about sums of contiguous subsequences, then you _can_ feasibly construct the entire array y, and **Rysto** ’s solution is a fairly efficient one. [Although it seems to me the array y will have size on the order of n^2, and so the running time will be on the order of n^2 log(n) rather than n log(n). Where are people getting that the list will be of length 2n? Won’t there be n\*(n-1)/2 possible contiguous subsequences?] ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [September 8, 2007, 9:52pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/11 "2007-09-08T21:52:35Z")
So does the y-array represent the sorted smallest sums of items in the x-array? For example, if x[k] is {1,3,5,8,19} y[k] is {1, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14, 16, 17, 19… 36} ? Is a sort necessary? If you wanted to know if, say, 25 was a possible y-value, a recursive algorithm could tell you quickly enough. 25 in fact _is_ valid, though 26 is not. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 8, 2007, 9:55pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/12 "2007-09-08T21:55:28Z")
[QUOTE=Bryan Ekers] If you wanted to know if, say, 25 was a possible y-value, a recursive algorithm could tell you quickly enough. [/QUOTE] With arbitrary subsets, it could? As **ultrafilter** points out, [the subset-sum problem](http://en.wikipedia.org/wiki/Subset_sum) is NP-complete. Well, I suppose what you’re saying is that, for small values like 25, you could find out fast enough. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 8, 2007, 10:04pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/13 "2007-09-08T22:04:46Z")
Er, edit window lost. Well, I suppose what you’re saying is that, for small values like 25, you could find out fast enough. But he wants the first 100 to 1000 values of y, for which I don’t think things will be so fast. ---
**Author:** ![Digital\_Stimulus](https://avatars.discourse-cdn.com/v4/letter/d/aeb1de/32.png) [@Digital\_Stimulus](https://boards.straightdope.com/u/Digital_Stimulus)\ **Post date:** [September 8, 2007, 10:17pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/14 "2007-09-08T22:17:29Z")
[QUOTE=Polerius] I want to sort sum x\_k, where k belongs to a subset of {1,…,N} over all subsets of {1,…,N} [/quote] I’m sorry if I’m being dense but, for clarification, are you (effectively) talking about generating the power set of {1,…,N}? And that the sums under consideration will always begin with 1 (i.e., not an arbitrary starting point)? I used the word “effectively” because you’d be adding the elements of each produced subset rather than simply enumerating them. I do realize there’s an additional constraint of producing an ordered list of the sums (which might be useful in predetermining a cutoff point), but I just wanted to be clear. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 8, 2007, 10:47pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/15 "2007-09-08T22:47:55Z")
Anyone want to take a crack at determining the running time of a divide-and-conquer algorithm using lazy lists/streams? I’m interested in how long this takes to generate the first k elements of output. Specifically, you take the original list, split it into two roughly equal parts, and recursively obtain (duplicate-free, ordered) streams for the sums from those two parts (call these the a-stream and the b-stream). Then, one takes each element from the a-stream and maps it with addition over the b-stream, giving a, uh, stream of streams, each of which is duplicate-free and ordered. One can merge these in any classical fashion, and the result is the desired stream of sums from the powerset of the original list. If it’s not clear what I’m talking about, here’s some Haskell code: ```auto --Splits a list [x1, x2, x3, x4, ...] into ([x1, x3, ...], [x2, x4, ...]) split [] = ([], []) split (x:xs) = let (a, b) = split xs in (x:b, a) --Standard function for merging two ordered duplicate-free lists merge [] yl = yl merge xl [] = xl merge xl@(x:xs) yl@(y:ys) | x < y = x:(merge xs yl) | x == y = x:(merge xs ys) | x > y = y:(merge xl ys) --This function merges many ordered duplicate-free lists at once --I know merging of many lists can be done more efficiently than this -- (by keeping the lists in a priority queue ordered by their first element) mergemany = foldl merge [] --This function produces an ordered duplicate-free list of all the sums -- of the powerset of a given list sums [] = [0] sums [0] = [0] sums [x] = [0, x] sums xs = let (a, b) = split xs (asums, bsums) = (sums a, sums b) sumtable = [map (+x) bsums | x <- asums] in mergemany sumtable ``` ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 8, 2007, 10:55pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/16 "2007-09-08T22:55:00Z")
Hm, I suppose the above code isn’t sufficiently lazy to do what I wanted with the efficiency I wanted it to. Feel free to ignore it while I try to improve it, if such improvement is possible. ---
**Author:** ![Rysto](https://avatars.discourse-cdn.com/v4/letter/r/ecccb3/32.png) [@Rysto](https://boards.straightdope.com/u/Rysto)\ **Post date:** [September 8, 2007, 11:53pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/17 "2007-09-08T23:53:17Z")
Ok, working from the assumption that x[1] + x[3] is not a valid sum(ie only sums from 1 to k, where 1 \<= k \<= N, are valid), here’s an algorithm to do it in O(M) time: x[1…N] is our original(sorted) sequence. To construct the sequence we want, a, perform the following algorithm: ```auto j = 1; k = 3; nextSum = x[1] + x[2] for i from 1 to M do if(x[j] <= nextSum) then a* = x[j]; j = j + 1; else a* = nextSum; nextSum = nextSum + x[k]; k = k + 1; end if end for ``` Things get a bit trickier if we need to allow negative numbers, but it’s still doable. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 9, 2007, 12:57am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/18 "2007-09-09T00:57:08Z")
So you’re saying, **Rysto** , that you’re considering both A) singletons from the original list (i.e., x\_k for any k) and B) sums over initial segments of the original list (i.e., x\_1 + x\_2 + … + x\_k for any k)? It’s a bit odd if that’s what the OP wants, but all his examples _were_ of that form. So, again, I call upon the OP to clarify: what kinds of sums do you want? Sums over arbitrary subsets of the original list (as seems indicated by your wording)? Subsets over contiguous subsets of the original list? Sums over both singletons and initial segments of the original list (as indicated by your examples, on one interpretation)? The answer to your question is, clearly, highly dependent upon, well, what your question is about, exactly. ---
**Author:** ![Polerius](https://avatars.discourse-cdn.com/v4/letter/p/d78d45/32.png) [@Polerius](https://boards.straightdope.com/u/Polerius)\ **Post date:** [September 9, 2007, 7:03am UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/19 "2007-09-09T07:03:10Z")
[QUOTE=Indistinguishable] So, again, I call upon the OP to clarify: what kinds of sums do you want? Sums over arbitrary subsets of the original list (as seems indicated by your wording)? [/QUOTE] Yes. > [@](#): > > Subsets over contiguous subsets of the original list? Sums over both singletons and initial segments of the original list (as indicated by your examples, on one interpretation)? No. I’m not sure how the “contiguous subset” constraint suddenly surfaced, since I don’t mention it in the wording of the problem > [@](#): > > I want to sort > sum x\_k, where k belongs to a subset of {1,…,N} > **over all subsets** of {1,…,N} Sorry if my examples were misleading. They may have been misleading because they are examples about the first few terms of the sequence Later on, the sequence might look like x[4]+x[8] x[3]+x[4]+x[7] x[4]+x[9] … Just take _all_ the subsets of {1,…,N}, calculate sum x[k], and sort the result, i.e. rank the subsets in order of increasing sum x[k]. The problem is coming up with an algorithm that finds the first M subsets, without having to calculate sum x[k] for all 2^N subsets ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [September 10, 2007, 8:05pm UTC](https://boards.straightdope.com/t/sorting-algorithm-question/418443/20 "2007-09-10T20:05:34Z")
Since your values x[1],…,x[N] are all positive, the formal subset sums immediately generate a poset lattice with bottom 0 and top x[1]+…+x[N]. You can think of this lattice as the vertices of an N-dimensional hypercube {0,1}[sup]N[/sup], with each dimension representing the absence (0) or presence (1) of one of the values (so vertex \<01101\> represents the sum x[2]+x[3]+x[5]). The edges of the hypercube represent transitions with Hamming weight 1: i.e., changing a vertex sum by adding or removing one value. The “upward neighbors” (those at the other end of an upward edge) are those which result from changing a single “0” to a “1”. You want to generate sums upward from the bottom. Maintain two data structures: a list minimal-sums (which will become your desired output, and can just be a linked list) and a set possible-next-sums (which should be able to efficiently maintain a sorted state on random-access insertion and deletion). Begin with both of these structures empty. Start at the bottom vertex \<0…0\>=0. Now repeat, M+1 times (the first time through just gives you 0; the next M times give you the lowest M sums):[ol][li]Append \=s to minimal-sums.[/li][li]Insert all upward neighbors of \=s into possible-next-sums (unless already present).[/li][li]Find a minimal sum \=s in possible-next-sums.[/li][li]Remove \=s from possible-next-sums.[/ol]You can end the final iteration after step 1 if you want.[/li] The set possible-next-sums will usually get large, eventually. But since each vertex has only O(N) upward neighbors, in M steps it will only get to size O(MN). Efficient access, insertion, and deletion into such a set should be O(log MN). So each iteration should take[ol][li]O(1)[/li][li]O(N log MN)[/li][li]O(log MN)[/li][li]O(log MN)[/ol]and the overall algorithm should run in O(MN log MN).[/li] For example, with values {2,3,5,7,15} and M=5 (showing the last element of minimal-sums and the set possible-next-sums at the end of step 2 each time through the loop): ```auto 0=<00000> 2: <10000> 3: <01000> 5: <00100> 7: <00010> 15: <00001> 2=<10000> 3: <01000> 5: <00100> <11000> 7: <00010> <10100> 9: <10010> 15: <00001> 17: <10001> 3=<01000> 5: <00100> <11000> 7: <00010> <10100> 8: <01100> 9: <10010> 10: <01010> 15: <00001> 17: <10001> 18: <01001> 5=<11000> 5: <00100> 7: <00010> <10100> 8: <01100> 9: <10010> 10: <01010> <11100> 12: <11010> 15: <00001> 17: <10001> 18: <01001> 20: <11001> 5=<00100> 7: <00010> <10100> 8: <01100> 9: <10010> 10: <01010> <11100> 12: <11010> <00110> 15: <00001> 17: <10001> 18: <01001> 20: <11001> <00101> 7=<10100> 7: <00010> 8: <01100> 9: <10010> 10: <01010> <11100> 12: <11010> <00110> 14: <10110> 15: <00001> 17: <10001> 18: <01001> 20: <11001> <00101> 22: <10101> ``` (the next sum is 7=\<00010\>). [Next page](https://boards.straightdope.com/t/sorting-algorithm-question/418443.md?page=2)