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

In summary, the conversation is about finding an algorithm to efficiently generate subsets from a multiset in ascending order based on the sums of their elements. The goal is to avoid generating all combinations and instead find a way to generate them in the desired order to minimize computational cost. Sorting algorithms were suggested as a possible solution, but it was noted that sorting after generation may still be necessary and generation is the main cost in this process.
  • #1
Moni
181
1
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?
 
Physics news on Phys.org
  • #2
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?
 
  • #3
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!
 
  • #4
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.
 

1. What is the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet"?

The "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" refers to the arrangement of the sub(multi)set of a MultiSet in increasing order based on the sum of its elements. This is a mathematical concept used in data analysis and statistics.

2. How is the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" calculated?

The calculation of the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" involves finding the sum of each sub(multi)set's elements and arranging them in ascending order. This can be done manually or with the help of computer programs.

3. What is the significance of the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" in scientific research?

The "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" is used to analyze and compare data sets in various scientific research fields. It helps in identifying patterns, trends, and outliers in the data, which can provide valuable insights and aid in making informed decisions.

4. Can the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" be used for any type of data?

Yes, the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" can be used for any type of data that can be organized into a MultiSet. This includes numerical, categorical, and even textual data.

5. Are there any limitations to using the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" in data analysis?

While the "Ascending Order of the Sums of the Elements of the Sub(multi)set of MultiSet" is a useful tool in data analysis, it may not be suitable for all types of data. For example, if the data set has a large number of elements or if there are significant variations in the size of the sub(multi)sets, the results may not accurately represent the data.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
605
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
57
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Back
Top