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

  • Thread starter Moni
  • Start date
181
1
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

Mentor
Insights Author
2018 Award
10,740
7,366
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?
 
181
1
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

Mentor
Insights Author
2018 Award
10,740
7,366
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.
 

Want to reply to this thread?

"Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top