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:

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

  • 3
    $\begingroup$ It is unclear to me (even with your examples) what you really want. Also, I suspect this forum is the wrong one for your question. If you want to omit duplicates, multiply and then add, say replace with 2000,4000,4001,4002,5000,..., to get rid of duplicates while attempting to preserve some part of sum order. Gerhard "On Some Problems, Go Big" Paseman, 2019.04.15. $\endgroup$ – Gerhard Paseman Apr 15 '19 at 20:26
  • $\begingroup$ In particular, it's not clear to me what "subset sum ascending ordering" means. $\endgroup$ – Gerry Myerson Apr 15 '19 at 23:49
  • $\begingroup$ Ok, I think I should edit a bit to make it more clear: In the initial set (A) I am generating all the subsets of A...in the order (ascending) of their sum. And in the modified version I also want to keep that order from the original but getting rid of the repetition of numbers. $\endgroup$ – Moni Apr 16 '19 at 0:31
  • $\begingroup$ Let's call your initial sequence $a_i$ and the new sequence $b_i$. Two clarifications: (1) if $\sum_{i\in I} a_i = \sum_{j\in J} a_j$ must $\sum_{i\in I} b_i = \sum_{j\in J} b_j$? (2) If $\sum_{i\in I} a_i < \sum_{j\in J} a_j$ is the condition that $\sum_{i\in I} b_i < \sum_{j\in J} b_j$ or that $\sum_{i\in I} b_i \leq \sum_{j\in J} b_j$? $\endgroup$ – Daniel McLaury Apr 16 '19 at 13:05

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.