3
$\begingroup$

In this question the number of unique sortings has been discussed.

As a follow-up, I would like to know, whether the problem of sorting the sequence of subset sums has ever been studied.
There should different algorithms for the case of only positive element-weights and for positive and negative element weights.

In analogy to the "ordinary" sorting problem, I would expect a variety of solutions to exist, addressing either simplicity of formulation (Bubblesort), practical applicability (Quicksort) and worst-case optimality (Heapsort).

Question::
is there a technical term for the problem and, what would be good ressources for it?

Improve this question
$\endgroup$
4
  • $\begingroup$ Not every question involving the term "set" is a set theory question. $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 22, 2016 at 7:53
  • $\begingroup$ What is the output? Is the sum uniqueness of the other problem present in this one? Is there any practical reason to consider an implementation other than Mergesorting sorted S_k and S_k+a_{k+1}? (Are the a_k of the underlying set even available?) I understand my idea of the problem,but I suspect it is different from your idea. Gerhard "Wonders How Result Is Used" Paseman, 2016.03.22. $\endgroup$
    – Gerhard Paseman
    Commented Mar 22, 2016 at 15:19
  • $\begingroup$ The assumption I make, is that all subset subset sums are distinct and that the pairs of subsets and their weight sums are available. The task is then to sort the weights in w.l.o.g. ascending order. Especially in the case of positive element weights, one could exploit containment relations between subsets to reduce the number of required comparisons and I would like to see algorithms which do that systematically. $\endgroup$
    – Manfred Weis
    Commented Mar 22, 2016 at 15:41
  • $\begingroup$ For the positive weight case, one pass through all the $2^n$ sums to determine the n weights, followed by a recalculation of all the sums, can be done in $O(n2^n)$ steps and likely fewer. There may be a way to relabel things to reduce the general case to the case of positive weights. The distinct sums assumption is strong and may get you some fast solutions. Gerhard "Likes Quick And Easy Sometimes" Paseman, 2016.03.22. $\endgroup$
    – Gerhard Paseman
    Commented Mar 22, 2016 at 19:52

2 Answers 2

Reset to default
1
$\begingroup$

One standard situation where sorted subset sums comes up is in the subset sum problem. (I.e. is zero among the subset sums of a given set?) By splitting the input into two equinumerous subsets, sorting the subset sums of each subset, and comparing the two lists of sorted subset sums, it is possible to solve the problem in time proportional to roughly $2^{n/2}$ (where $n$ is the number of given values) rather than the naive bound of $2^n$.

According to Wikipedia this idea is due to Horowitz and Sahni in 1972; see the link for references.

As for your idea that all-positive should be easier than unconstrained values: I don't think so. If you add the same large value to all inputs, it makes them all positive without changing the solution much (you can decompose the result into a linear number of subsequences within which all sums have been changed in the same way, then merge these subsequences to get the sorted order of your original input, only increasing the complexity by a small amount).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Prior to finding the solution sketched in my answer, I thought that negative weights would make a difference; that was because I had thought about adding a constant value to the element weights, but not about adding the value to the subsets sums. But still the idea of adding a constant to the subset sums only works for finite sets, whereas the sketched solution also works for infinite sets with no restrictions on element weights and, it also allows one to find a pair subsets of equal weight in finite time in that case, but of course, it can't prove the absence of such a pair. $\endgroup$
    – Manfred Weis
    Commented Mar 28, 2016 at 8:18
  • $\begingroup$ Another observation is, that the complexity of generating the subset sums in sorted order isn't $O(n2^n)$ as would follow from sorting the sequence of subset sums, but rather $O(2^n)$ and I wonder, if that would lead to a better complexity estimate of the Horowitz and Sahni algorithm. At least it indicates that the naive complexity bound for subset sum sorting is wrong by a factor of $log(m)$ with $m:=2^n$ $\endgroup$
    – Manfred Weis
    Commented Mar 28, 2016 at 8:32
0
$\begingroup$

After some fruitless efforts to devise a tree-structure based on subset inclusion and after some investigations on the usability of de Bruijn sequences, I finally arrived at a surprisingly simple method, that is also applicable to countably infinite sets of values:

let $\omega(\sigma)\in\mathbb{R};\ \omega(\emptyset):=0$ the function, that assigns a real weight to each subset.

let $(\lbrace a_0\rbrace:=\lbrace\emptyset\rbrace,\lbrace a_1\rbrace,\lbrace a_2\rbrace,\ ...\ )$ be the sequence of sets containing as elements the empty set, resp. the elements of the "base set".

if $(\Omega_{i,0},\ ...\ \Omega_{i,2^{i-1}}) $ denotes the ordered sequence of all subset sums of $(\lbrace a_0\rbrace,\ ...\ \lbrace a_i\rbrace)$
then $(\Omega_{i+1,0},\ ...\ \Omega_{i+1,2^i}) $ is the merge-sorted union
$(\Omega_{i,0},\ ...\ \Omega_{i,2^{i-1}}) \cup (\Omega_{i,0}+\omega(\lbrace a_{i+1}\rbrace),\ ...\ \Omega_{i,2^{i-1}}+\omega(\lbrace a_{i+1}\rbrace)) $

The sketched algorithm also indicates, that its complexity is $O(2^n)$ if the base set contains $n$ elements. If the subset sums are not unique, then duplicates can be skipped without extra effort in the merging process (in that case the index ranges of the sketched algorithm are of course different).

I'm aware that the notation may need improvement; please feel free to edit or suggest improvements.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .