Math-sy question

Cheetah Designs

Cheetah Designs

Cheetah Designs

Associate
Joined
10 Jul 2006
Posts
2,423
I have a set of numbers {0, 1, 2, 3, ..., 49}

How do I get every every possible subset of numbers where the set length is between 5->10?

So these will all be included:

{0, 1, 2, 3, 4}
{5, 7, 20, 25, 49}
{4, 7, 12, 48, 49}

I'm looking for the general trail of though of the method/algorithm you use.
 
49! - 44!


edit: this is wrong, only works for subsets of 5 numbers.
for subsets ranging from 5 - 10, you need to do:

49! - 44! (all subsets 5 numbers long)
+
49! - 43! (all subsets 6 numbers long)
+
49! - 42! (all subsets 7 numbers long)
+
49! - 41! (all subsets 8 numbers long)
+
49! - 40! (all subsets 9 numbers long)
+
49! - 39! (all subsets 10 numbers long)
= (a very big number)
 
Last edited:
Start with a set length of 2...

so:
1,2
1,3
1,4
1,5
..
1,49
2,3
2,4
...
etc...

Then advance each to a lenght of 3, so the above becomes

1,2,3
1,2,4
...
1,2,49
1,3,4

and then carry on...

Note, I'm assuming you cannot have 1,4,3 in your list - if not, then differ slightly

edit: d'oh!
 
touch said:
49! - 44!


edit: this is wrong, only works for subsets of 5 numbers.
for subsets ranging from 5 - 10, you need to do:

49! - 44! (all subsets 5 numbers long)
+
49! - 43! (all subsets 6 numbers long)
+
49! - 42! (all subsets 7 numbers long)
+
49! - 41! (all subsets 8 numbers long)
+
49! - 40! (all subsets 9 numbers long)
+
49! - 39! (all subsets 10 numbers long)
= (a very big number)
Click to expand...

that includes permutations that are the same subset though.

e.g. 1,2,3,4,5 = 5,4,3,2,1 in terms of a sub set, although the permutation is different. As op asked for all subsets, then the number he is after is smaller than your answer.

Isn't the answer then

49 choose 5 +
49 choose 6 +
... +
49 choose 10

?
 
Last edited:
Amleto said:
that includes permutations that are the same subset though.

e.g. 1,2,3,4,5 = 5,4,3,2,1 in terms of a sub set, although the permutation is different. As op asked for all subsets, then the number he is after is smaller than your answer.

Isn't the answer then

49 choose 5 +
49 choose 6 +
... +
49 choose 10

?
Click to expand...

Correct! edit: Oops but 50 as below :D
 
To calculate the amount of subsets, we need to use combinations.

To find the number of r sized subsets from an n sized set, we calculate nCr where nCr = n!/[r!(n-r)!]

You're including 0, so our n is 50.

5-sized subsets : 50C5 = 50!/[5!*45!] = (50*49*48*47*46)/(5*4*3*2*1) = 2118760.
6-sized subsets : 50C6 = 50!/[6!*44!] = 15890700
7-sized subsets : 50C7 = 50!/[7!*43!] = 99884400
8-sized subsets : 50C8 = 50!/[8!*42] = 536878650
9-sized subsets : 50C9 = 50!/[9!*41!] = 2505433700
10-sized subsets : 50C10 = 50!/[10!*40!] = 10272278170

Add them up and it turns out that from your set of 50 elements there are 13,432,484,380 subsets that have between 5 and 10 elements.
 
i believe the answer you're looking for is

50C5 + 50C6 + 50C7 + 50C8 + 50C9 + 50C10

i'll edit the answer to that when i can find my calculator

*edit*
beaten like a ginger step child
 
Last edited:
Wait are you looking for the number of combinations or are you looking for pseudocode to actually generate them?
 
Alex74 said:
Wait are you looking for the number of combinations or are you looking for pseudocode to actually generate them?
Click to expand...

if you want the algorithm to generate the combinations then a simple (but probably not very efficient) way of doing it would be to daisy chain some counters. and store each result. i.e. the when the first number has counted from 0-49 add 1 to the second number.

after each combination has been done, check that the first number is greater than the second number, the second is greater than the third, etc, etc, until the last number. if the numbers are in descending order then you wont have had a repeated combination and can store it in a (rather large) array.

there might be a way of including all 5 sets in one algorithm, but i cant think of a simple way of doing that, so a separate version of this algorithm would be needed for each set of numbers
 
Reaper 392 said:
if you want the algorithm to generate the combinations then a simple (but probably not very efficient) way of doing it would be to daisy chain some counters. and store each result. i.e. the when the first number has counted from 0-49 add 1 to the second number.

after each combination has been done, check that the first number is greater than the second number, the second is greater than the third, etc, etc, until the last number. if the numbers are in descending order then you wont have had a repeated combination and can store it in a (rather large) array.

there might be a way of including all 5 sets in one algorithm, but i cant think of a simple way of doing that, so a separate version of this algorithm would be needed for each set of numbers
Click to expand...

Yea you might be right, have the algorithm to generate the 50ChooseN combinations, and do it seperately for N = 5,..,10.

You're definitely looking at N counters, storing the different combinations as you iterate over them. Can post in more detail if needed :)
 
make a starting sub set
{01,2,3,4}

then working from the end index, repeatedly add one until the number isnt in the set [0,49], then add one to the previous, and reset the end index to 'previous + 1'

{0,1,2,3,5}
{0,1,2,3,6}
...
{0,1,2,3,49}
{0,1,2,4,5}
{0,1,2,4,6}
...

when the 4th index finally turns into 48 and the the fifth index is 49, then you add one to the 'previous previous index'

ie
// here, 48 cant jump up to 49 because we have already gone through all {0,1,2,49,x} subsets
{0,1,2,48,49}
{0,1,3,4,5} << lowest possible starting point for {0,1,3,x,y}

e: 'we have already' is incorrect, but 'we will' go through all subsets anyway without this step.
 
Last edited:
Yes, i think a bunch of nested loops would be the easiest way to do it:
Code: 
LOOP 49
   LOOP 49
      LOOP 49
         LOOP 49
            LOOP 49
            OUTPUT position in each loop
            ENDLOOP
         ENDLOOP
      ENDLOOP
   ENDLOOP
ENDLOOP

That would be the sort of thing to output all sets 5 numbers long.
 
Last edited:
Alex74 said:
Yea you might be right, have the algorithm to generate the 50ChooseN combinations, and do it seperately for N = 5,..,10.

You're definitely looking at N counters, storing the different combinations as you iterate over them. Can post in more detail if needed :)
Click to expand...

good god, dont store the combinations! just iterate over them and count them.
 
touch said:
Yes, i think a bunch of nested loops would be the easiest way to do it:
Code:

That would be the sort of thing to output all sets 5 numbers long.
Click to expand...

It's a starting place, but by no means correct :p

for starters, {0,0,0,0,0} is not valid (your starting position), and nor is {0,1,2,4,0} (your roll-over is not correct).



e: I saw your ninja :p but hard-coded loop for 49 times isn't right either
 
Last edited:
Alex74 said:
Hehe well it seemed as though Cheetah wanted to use them for something :p counting them's easy, no reason to even bother with such an algorithm for that.
Click to expand...

well then you can output the 'next' value when requested. This only ever requires memory for one combination, which is slightly better than ~ 13 billion :D
 
Amleto said:
well then you can output the 'next' value when requested. This only ever requires memory for one combination, which is slightly better than ~ 13 billion :D
Click to expand...

In my defence i didnt actually count them :D but fair. Guess it depends what the OP wants to do with them :)
 
You must log in or register to reply here.
Back
Top Bottom