How do you write an algorithm to find the number of permutations or combinations?

Answer 1

Permutations and combinations are two separate things. Although we often use them interchangeably in English, we need a more precise definition in mathematics, such that ABC and CBA are regarded as being two different permutations of the same combination. In other words, the order of the elements is important in a permutation but is completely irrelevant in a combination.

First we have to define what it means to create a combination or permutation. Typically we have a set from which we must make a subset. The number of elements in the set is typically defined using the variable n while the number of elements in the subset is r. Thus we can formally define a permutation mathematically using the function P(n,r) and a combination as C(n,r).

We must also consider whether elements may be repeated within a combination or a permutation. For instance, when selecting numbers for a lottery, no number may be repeated in any combination but in a 4-digit combination lock, any digit may be repeated in a permutation.

Note that a combination lock is really a permutation lock in mathematics and is the perverse way of remembering the mathematical difference between a combination and a permutation.

Thus we have 4 possible variations to cater for. In order of difficulty, they are:

1. Permutations with repetition
2. Permutations without repetition
3. Combinations without repetition
4. Combinations with repetition

Let's deal with them one at a time.

1. Permutations with repetition

To calculate P(n,r) with repetitions, for every selection, r, there are always n possibilities, thus we have n^r permutations.

In a 3-digit combination lock, each digit has ten possibilities, 0 through 9, so there are 10^3=10x10x10=1000 permutations. This stands to reason because the permutations form all of the numeric values from 000 through to 999, which is 1000 different values.

In C, we can write this function as:

unsigned long long permutations (unsigned long long n, unsigned long long r) {

return pow(n,r); /* use standard library function */

}

2. Permutations without repetition

To calculate P(n,r) without repetitions we must reduce the set by one element each time we make a selection. If we go back to our 3-digit combination lock, we have 10 choices for the first digit which leaves 9 choices for the next and 8 for the next. So instead of 10x10x10=1000 permutations we only have 10x9x8=720 permutations.

Although fairly simple to work out in this case, we need a formula that is generalised to cater for all cases, just as n^r works for all permutations with repetitions.

We can see that 10x9x8 is the initial product of 10! (factorial 10) which is 10x9x8x7x6x5x4x3x2x1. So we need a formula that ignores everything after the 8. The portion after the 8 is 7x6x5x4x3x2x1 which is 7! and we can calculate that from (n-r)!=(10-3)!=7!

Having determined the portion we need to ignore, the rules of multiplication and division state that if we multiply by x and subsequently divide by x, then the two x's must cancel each other out. Thus we get:

10!/7!=(10x9x8x7!)/7!=10x9x8=720

Using formal notation, P(n,r) without repetition is therefore n!/(n-r)!

In C, we must first write a function to calculate factorials:

unsigned long long factorial (unsigned long long n) {

return (n>1)?factorial(n-1):1; /* recursive function */

}

With that in place, we can now write a function to handle permutations without repetitions:

unsigned long long permutations_norep (unsigned long long n, unsigned long long r) {

return factorial(n)/factorial(n-r);

}

3. Combinations without repetition

C(n,r) without repetition is simply an extension of P(n,r) without repetition. Every combination of r has r! permutations, so if we divide P(n,r) by r! we will get C(n,r). Expressing this formally, C(n,r) without repetition is n!/((n-r)!r!)

Going back to our 3-digits from 10, there are 10!/((10-3)!3!)=10!/(7!3!)=(10x9x8x7!)/(7!3!)=(10x9x8)/3!=720/6=120 combinations without repetition.

Using the factorial function shown above, we can write a C function to handle combinations without repetition:

unsigned long long combinations_norep (unsigned long long n, unsigned long long r) {

return factorial(n)/(factorial(n-r)*factorial(r));

}

4. Combinations with repetition

Combinations with repetition is the hardest concept to wrap your head around.

Going back to our 3-digits from 10, let's begin enumerating all the combinations so we can verify the answer at the end. We start by enumerating all those that combinations that begin with a 0:

000, 001, 002, 003, 004, 005, 006, 007, 008, 009

011, 012, 013, 014, 015, 016, 017, 018, 019

022, 023, 024, 025, 026, 027, 028, 029

033, 034, 035, 036, 037, 038, 039

044, 045, 046, 047, 048, 049

055, 056, 057, 058, 059

066, 067, 068, 069

077, 078, 079

088, 089

099

Note that there is no 010 because it is a permutation of 001. Similarly with 021 which is a permutation of 012. As a result of this, each row has one less combination than the one above. Thus there are 10+9+8+7+6+5+4+3+2+1=55 combinations.

If we now enumerate all those that begin with a 1, we see a similar pattern emerges:

111, 112, 113, 114, 115, 116, 117, 118, 119

122, 123, 124, 125, 126, 127, 128, 129

133, 134, 135, 136, 137, 138, 139

144, 145, 146, 147, 148, 149

155, 156, 157, 158, 159

166, 167, 168, 169

177, 178, 179

188, 189

199

This time we have 9+8+7+6+5+4+3+2+1=45 combinations.

Following the same logic, the next section must have 8+7+6+5+4+3+2+1=36 combinations, followed by 28, 21, 15, 10, 6, 3 and finally 1. Thus there are 220 combinations in total.

The formula to work this out is quite complex, however it becomes simpler when we look at the problem in a different way. Suppose we have 10 boxes and each box holds at least 3 of the same digit. We can number these boxes 0 through 9 according to those digits. Let us also suppose that we can only move in one direction, from box 0 to box 9, and we must stop at every box along the way. This means we must make 9 transitions from one box to the next.

While we along the row, we carry a tray with 3 slots. Whenever we stop at a box (including box 0 where we start from) we can either pick a number from the box or we can move onto the next box. if we pick a number, we place it in the first slot. We can then pick another or we can move on. When we have filled all the slots, we simply move on until we reach box 9. If we reach box 9 and still have slots available, we must pick as many 9s as we need to fill the remaining slots.

It probably sounds far more complex than it really is. By imagining a selection being done this way we can create a convenient binary notation. For instance, if we say that 1 means pick a number and 0 means move onto the next box, the sequence 101010000000 would tell us we selected the combination 123 while the sequence 000000000111 tells us we selected 999. Every combination is therefore reduced to 12-bit value containing exactly three 1s and nine 0s, and it is these specific combinations we are actually looking for.

C(n,r) with repetition is formally expressed as (r+n-1)!/(r!(n-1)!)

If we plug in the actual numbers we find:

=(3+10-1)!/(3!(10-1)!)

=12!/(3!9!)

=(12x11x10x9!)/(3!9!)

=(12x11x10)/3!

=1320/(3x2x1)

=1320/6

=220 combinations with repetition.

This type of problem might be expressed in other ways. For example, how many different ways can we fill a box with 100 sweets from 30 different sweets. C(n,r) is C(30,100) thus we find:

=(100+30-1)!/(100!(30-1)!)

=129!/(100!29!)

=(129x128x127x...x101x100!)/(100!29!)

=(129x128x127x...x101)/29!

=5.3302324527079900778691094496787e+59/8,841,761,993,739,701,954,543,616,000,000

=60,284,731,216,266,553,294,577,246,880 combinations with repetition.

In C we can use the following function in conjunction with the factorial function shown earlier:

unsigned long long combinations (unsigned long long n, unsigned long long r) {

return factorial(n+r-1)/(factorial(r)*factorial(n-1));

}

We might also have similar problems with an additional restriction. For instance, we might be asked to select 100 sweets from 30 different sweets selecting at least 1 of each type. This reduces the number of slots to 100-30=70 but we have the same number of transitions, so we get:

=(70+30-1)!/(100!(30-1)!)

=99!/(70!29!)

=(99x98x97x...x71x70!)/(70!29!)

=(99x98x97x...x71)/29!

=7.7910971370578048745872324992773e+55/8,841,761,993,739,701,954,543,616,000,000

=8,811,701,946,483,283,447,189,128 combinations with repetition.

To accommodate this caveat, we can use the following function instead:

unsigned long long combinations2 (unsigned long long n, unsigned long long r) {

return factorial(n-1)/(factorial(r)*factorial(n-1));

}