1
$\begingroup$

Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions:

  • Element values range between 0-11
  • Set length is between 1-12
  • All sets must begin with 0 ([ 0 ])
  • Value of element n must be greater than value of element n-1

I want to generate every possible combination of sets with those conditions. So here's a few examples:

[ 0 ], [ 0, 1 ], [ 0, 2 ], [ 0, 3, 5 ], [ 0, 8, 9, 11 ]

All the way to:

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]

The main language I'm using is Javascript, but if you're use to dealing with C/C++/Python examples in those languages work too. Just no ASM or Perl please. :)

$\endgroup$
  • $\begingroup$ The question is on-topic but not the language :) This site would just be about describing the algorithm. $\endgroup$ – 6005 Apr 4 at 11:37
0
$\begingroup$

Let $k = 11$ in your problem, so we want to generate all sets with values in the range $0$ to $k$ and with between $1$ and $12$ elements. Then you can do the following:

  • First generate all sets for $k-1$ (recursively)

  • Then, for each set, make two copies, one with a $k$ on the end and one without a $k$ on the end.

If you prefer doing it iteratively, here is this described in an iterative fashion (pseudocode):

generate_all_subsets(k):
    let sets = [[0]]
    for i from 1 to k:
        for each set in sets:
            add sets + [k] to sets
            # (now there are two copies: sets, and sets + [k],
            #  so the size of 'sets' has doubled)
    return sets
| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.