A Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet

[Moni]

TL;DR Summary

Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Sub(multi)set

Summary: Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Sub(multi)set

I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed.
For example you have a set S = {1,2,2,3,4,5,5}
So, rather than generating all the combinations based on number of items (say start with 1 and 2 items and finally all 7) I want to figure them out in this order:
{1}, {2}, {2}, {1,2}, {1,2}, {3}, {1,3}, {2,2}, {4}.....{1,2,2,3,4,5,5}
Why this order: Well taking sum of these subsets we can see:
{1}, {2}, {2}, {3}, {3}, {3}, {4}, {4}, {4}.....{22}
Do you know any algorithm which can do it efficiently?

 

[fresh_42]

I'm not sure how you arrived at the copies of those singlets, i.e. how you distinguish the elements in $S$ if they have the same name? That's nothing the $\{\,\,\}$ notation allows.

Anyway, why don't you use one of the usual sort algorithms?

 

[Moni]

Hi, yes sorting algorithms can be used, but then you need to generate all of the combinations and then sort it. But the project I am working on, there the result might be available in the first 25% of the numbers (80% of the time) that means if you have say, 100 submultisets (powerset) and if you can generate that sequence (their sums ascending ordering) then you might get the desired combination (submultiset) within first 25 generated ones. Generating all of them in those cases is computationally expensive!

 

[fresh_42]

You can sort them right after generation, which is cheap. That leaves us with the question,whether generation has to be done or not. However, they occur in your final list, so they will have to be produced at some stage. Hence generation is the only and unavoidable cost.