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???

  • $\begingroup$ 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$? $\endgroup$ – Theo Bendit Apr 16 at 0:33
  • $\begingroup$ 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. $\endgroup$ – Moni Apr 16 at 0:54
  • $\begingroup$ Maybe you could edit the question to include the definition of the subset sum ordering? $\endgroup$ – Theo Bendit Apr 16 at 0:58
  • 1
    $\begingroup$ 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. $\endgroup$ – The Count Apr 16 at 1:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 16 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.