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. :)
-
$\begingroup$ The question is on-topic but not the language :) This site would just be about describing the algorithm. $\endgroup$Caleb Stanford– Caleb Stanford2020年04月04日 11:37:23 +00:00Commented Apr 4, 2020 at 11:37
1 Answer 1
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