Efficient Calculation of Combinations with a Fixed Number of Elements

[ryt]

[SOLVED] simple combinations problem

Homework Statement

what is 12. combination of combinations with 3 elements of 1,2,3,4,5,6,7 ?

Homework Equations

The Attempt at a Solution

i tried step by step
123 - 124 - 125 - 126 - 127 - 134 - 135 - 136 - ... - and finaly i arrived at 12. witch is 147

is there a way to calculate it faster?, not step by step

 

[e(ho0n3]

I guess you can quickly reason that there must be five that begin with 12, four that begin with 13 and three that begin with 14 the last one of which must end in 7.

To generalize, let L be a list of r-combinations of the integers n_1, n_2, ..., n_m (n_1 < n_2 < ... < n_m) ordered in increasing lexicographic order.

There will be m - r + 1 that begin with n_1...n_(r-2)n_(r-1), m - r that begin with n_1...n_(r-2)n_r, m - r - 1 that begin with n_1...n(r-2)n_(r+1), etc. Knowing this you can quickly find the ith component in the sequence.

 

[CompuChip]

I don't really understand the question.
If you want to make combinations of three elements with the numbers 1, 2, 3, 4, 5, 6, 7 in which a number may not occur more than once, you can do it like this:
Suppose you have three places, ..., and you want to put a number on each of them. For the first one, you can choose 1, 2, 3, 4, 5, 6 or 7, so 7 possibilities. After you have chosen a number, say 4, it looks like: 4.. and you must choose a number from 1, 2, 3, 5, 6 and 7 to put in the second spot. Whatever number you chose for the first, you have 6 possibilities left for the second number. Then for the last place, you have 5 possibilities left. The total number of possibilities is thus 7 x 6 x 5 = 210.

 

[ryt]

To generalize, let L be a list of r-combinations of the integers n_1, n_2, ..., n_m (n_1 < n_2 < ... < n_m) ordered in increasing lexicographic order.

There will be m - r + 1 that begin with n_1...n_(r-2)n_(r-1), m - r that begin with n_1...n_(r-2)n_r, m - r - 1 that begin with n_1...n(r-2)n_(r+1), etc. Knowing this you can quickly find the ith component in the sequence.

i think i understand, almost.
What is r? Is this total number of combinations?

 

[e(ho0n3]

r is the size of the combination; in your case 3.

 

[ryt]

thx

If you want to make combinations of three elements with the numbers 1, 2, 3, 4, 5, 6, 7 in which a number may not occur more than once, you can do it like this:
Suppose you have three places, ..., and you want to put a number on each of them. For the first one, you can choose 1, 2, 3, 4, 5, 6 or 7, so 7 possibilities. After you have chosen a number, say 4, it looks like: 4.. and you must choose a number from 1, 2, 3, 5, 6 and 7 to put in the second spot. Whatever number you chose for the first, you have 6 possibilities left for the second number. Then for the last place, you have 5 possibilities left. The total number of possibilities is thus 7 x 6 x 5 = 210.

might also help, thx

 

[CompuChip]

Ah, I think I understand it as well
Do note that you are missing some combinations now.
E.g. in the series
123 - 124 - 125 - 126 - 127 - 134 - 135 - 136 - ... -
you will never have 132, so you will have to use a slightly different reasoning in case the numbers don't have to be ordered.

 

[ryt]

now i came to a bigger problem, and i stuck.

what is the 197. combination of size 5 without repeating of elements a,b,c,d,e,f,g,h,i,j,k,l ?

 

[unplebeian]

12x11x10x9x8= 12! - 7!= 95040. Same way as before RYT. You don't really expect me to write them all down? The above shows that there are more than 197 combinations of size 5 possible.