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

  • 4
    $\begingroup$ Seems more like a programming question than a math question. $\endgroup$ – Gerry Myerson Nov 15 '18 at 5:41
  • $\begingroup$ Generate all subsets and sort them by the elements sum value. $\endgroup$ – Max Alekseyev Nov 15 '18 at 12:28
  • $\begingroup$ That'd be extremely costly operation. $\endgroup$ – Moni Nov 15 '18 at 19:23
  • $\begingroup$ @Moni: What is costly? You will need to generate all subsets anyway, and sorting will bring just a log() factor to that. $\endgroup$ – Max Alekseyev Nov 17 '18 at 19:09
  • $\begingroup$ @MaxAlekseyev Yes...but want to generate them in the ascending order so that if for many cases the answer (for which this has to generated) might come in the first quarters of numbers we may not need to generate all other 75% combinations. $\endgroup$ – Moni Nov 21 '18 at 18:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.