# Rewriting a set of integers to get rid of repetition but keeping subset sum ordering

Say, I have a set of 6 +ve integers sorted in ascending order:

$$A = \{2,4,4,4,5,7\}$$

Now to make it easier to deal with (Minimum one starts with 1) I deducted one from all of them:

$$\therefore B= \{1,3,3,3,4,6\}$$

Now what I am trying to do is get rid of the repetition of numbers and I tried by keeping one number (4) and the rest same numbers in the incremental way (4,5) and the increased amount (+2) is added to the following numbers (4,6) after that.

$$\therefore C = \{1,3,4,5,6,8\}$$

But I wanted to keep the subset sum ascending ordering, which seems like doesn't now hold. For example:

For Set A: $$(2), (4), (4), (4), (5), (2,4)...$$

Sums are: $$2,4,4,4,5,6 ...$$ (Which has the desired ascending order)

For Set C: $$(1), (3), (4), (1,3), (5), (6), (1,6).....$$

Sums are: $$1,3,4,4,5,6,7...$$ (Which has the desired ascending order)

Up to this point it is fine. But what if I want to generate them from the original set $$A$$, and the problem is the order doesn't not hold anymore!

For example:

For Set A: $$(2), (4), (4), (4), (5), (2,4)...$$

Now if we replace 2 with 1, 4 with (3,4,5), 5 with 8 and 7 with 8 (in short values of Set-A is being replaced by values of Set-C same position):

It becomes: $$(1), (3), (4), (5), (1,3)...$$

Now the sums are: $$1,3,4,5,4...$$ We see that subset sum ascending ordering doesn't hold any longer $$(..,4,5,4..)$$. (Which DOES NOT have the desired ascending order)

Now my question is: Is there any way I can get rid of the repetition numbers i.e. they will become unique and the subset sum ordering will remain intact???

• Hi Moni! Welcome to MSE. I'm confused about your question. What rules are you using in order to change your list of numbers? For example, if your list had $n$ numbers, what would be the issue with replacing it with $1, 2, \ldots, n$? – Theo Bendit Apr 16 at 0:33
• Thanks! Yes, you were right, I also thought about that, but if I do that, the relative differences will be lost: for example if {2,4} is my desired solution which is minimum (subset sum wise) and also satisfies certain function. – Moni Apr 16 at 0:54
• Maybe you could edit the question to include the definition of the subset sum ordering? – Theo Bendit Apr 16 at 0:58
• A "set" formally does not have repetition, FYI. So as sets, $\{4,4\}=\{4\}$. You have a "multiset". It doesn't really matter here, but just thought I'd mention it. – The Count Apr 16 at 1:07
• Subtracting $1$ from all the numbers will change the pattern of subset sums because it subtracts the number of elements from the sum. For example, $\{2,2,4,10\}$ has subset sums $\{0,2,4,6,8,10,12,14,16,18\}$ but $\{1,1,3,9\}$ has sums $\{0,1,2,3,4,5,9,10,11,12,13,14\}$. Note the gap from $5$ to $9$. Is this what you want? Then are you looking for the smallest multiset that can generate a set of subset sums? I also do not understand the ordering of the subset sums. Please clarify. – Ross Millikan Apr 16 at 1:14