2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Seems more like a programming question than a math question. $\endgroup$
    – Gerry Myerson
    Commented Nov 15, 2018 at 5:41
  • $\begingroup$ Generate all subsets and sort them by the elements sum value. $\endgroup$
    – Max Alekseyev
    Commented Nov 15, 2018 at 12:28
  • $\begingroup$ That'd be extremely costly operation. $\endgroup$
    – Moni
    Commented Nov 15, 2018 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
    Commented Nov 17, 2018 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
    Commented Nov 21, 2018 at 18:38

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .