Algorithms and combinatorics

Today I tried out some programming in C++ where the problem was to find an algorithm to solve a problem. I notice that it was a while since I did stuff like this on the university so this was some good exercise to refresh some mathematics. The problem read as follows:

Given a set of n numbers (1…n) write them in r positions. In how many ways can you do this based on the following criterias:

Uniqueness or non uniqueness: If we have uniqueness (U) then we cannot chose the same number several times.
Ordered: If the list should be ordered (O) we must write the numbers in either decreasing or increasing ( non – strictly ) order.
Thus we have four different cases to solve:

!U and !O
!U and O
U and !O
U and O
One theorem that is very useful here is the binomial theorem (or more to the point the binomial coefficient), which I in a way rediscovered without realizing at first when I looked at these problems.

The binomial coefficient is often written like this: C(n,r) which means In how many ways can we select r objects from a set of n ?

1. But in the first case where we should find how many ways we can write r numbers from n where the numbers are not unique and the order do not matter we easily see that we can chose the first number in n ways, but as we do not have to care about the order and we can take the same number again the second number can also be selected in n ways. So the answer is simply nr which in C/C++ programming can be written pow(n,r).

2. In the second case one condition is changed, the number must now be in order. This one is a bit trickier, lets get back to it later.

3. For the third case the numbers are unique but we do not have to write them in order. This is simple, for the first number we can select it in n ways, the second in (n-1) ways as we have alredy taken one away. So the solution is n·(n-1)·(n-2)·…·(n-r-1).

4. Now we are quite restricted as the numbers are unique and also have to be in order. Now we can apply the binomial coefficient when we realize that this is the same as asking us to select r numbers from the collection of n numbers, because when we select r numbers we have also selected a specific order.

The binominal coefficient is expanded like this:

C(n,r) = n!/((n-r)!·r!)

where n! means n factorial ( n·(n-1)·(n-2)·…·1 ).

If we now look back at the second problem again where we are in the same position as the fourth case but with the difference that the numbers are not unique. If we take an example with n=5 and r=3 we are thus going to write numbers in the range 1-5 where the numbers must be in order. For example 1,1,4 is one such solution. If we now just write the three selected numbers as three x: xxx we can use four | symbols to divide the groups of different numbers. So if I write:

xx|||x|

I mean the sequence 114 mentioned earlier, the two leftmost x’s represent the two 1’s and the last x represent the four which is why it’s located in the fourth space between the | symbols. Realizing this we can see that this problem can also simply be expressed using the binomial coefficient as we can say in how many ways can we insert the | symbols among the x’s ? We see that we have n-1 | symbols and r x symbols, so we can express the problem as in how many ways can we select r from r+n-1 objects. Thus C(r+n-1,r).

By the way another thing that is important to remember when you calculate this on a computer is that the factorials can be insanely large numbers, for example if we in our problem use n=95 and r=10 and we just use the binomial coefficient on this we end up with 95!/(85!·10!). 95! is actually an amazingly insanely huge number: 1.03·10148. For comparison the estimated number of atoms in the universe is somewhere around 1·1079. The number is also greater than what the normal datatypes in C++ can handle. So to solve this it’s important to not do this calculation first but to eliminate a large part of the factorial expansion using the denominator.

Lämna ett svar

E-postadressen publiceras inte. Obligatoriska fält är märkta *