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.

Peru 0.4.1

I once made an application for camera calibration and stereo calculations which I named Peru. The homepage can be found here:

Today I released a new version (0.4.1) with some small bugfixes. I just polish abit on it for fun sometimes and with long intervals there might be new releases. There are much to be improved and I have learned some things since I started this project but I would feel bad about just letting it die away… =) I have no idea if anyone is really using it for any good, but that has not been my main purpose for keeping it updated. But if someone finds it interesting thats a bonus of course =)

According to the statistics there are at least some downloads of it every month as can be seen here:

That number of people who can actually test it now might increase as I am now providing it in binary form in addition to the usual source release. But it’s just for linux of course, but it should be possible to compile for windows but as it’s never tested it will probably not work without some fixes.

Epkg

If you use Linux and compile some packages from sources I would like to recommend a solution I have been using for a couple of years that make it really easy to install and uninstall packages.

There is a small utility called epkg that can be downloaded from here.

Every time you now build a package you add the option ”--prefix=/usr/local/encap/packagename” to the ”configure” script. When running ”make install” the package will now be installed to this specific location. Now comes the magic, you run ”epkg -i packagename” and symlinks will be installed in the system locations for this package to the installed package in the encap directory. You easily uninstall the package later by running ”epkg -r packagename” and the symlinks are removed (but package is still located in the encap directory). Using this system you can easily try out different versions of one package for example and you don’t need to keep track of where you originally built the package from just to be able to uninstall things.

Additional note:

I usually get a problem with an error message ”! man: not an Encap link” when trying to install encap from source. The solution is to configure encap to use another man directory like this:

./configure --mandir=/usr/share/man

and after this run ”make install”.

Books and Electricity

Now with the high electricity costs here in Norway (the prices are doubled compared to last year) I thought it would be interesting to see how much I actually use on various things in my apartment. Today I connected it to the washing machine and found out the following: I used the economy program on 40℃ (1:30h) with 2:10h of drying ( I have a combined machine ). The effect peaked at 2651W / 11.63A and the total consumption was 3.30 KWh. The current price for electricity is now about 0.75NOK/KWh in addition to nettleie (whatever that is in English) at about 0.32NOK/KWh, so totally the price of one wash is about 3.50NOK which do not sounds that much really. I do about 2 washes a week so that would amount to about 364NOK a year. Not entirely correct however as the price varies over the seasons and also I do run 60℃ washes also of course which would be slightly more expensive I guess. Nevertheless this gives an approximate figure.

By the way I thought Norway was cheaper than Sweden for electricity but it seems that I was wrong, here is a graph over the prices per MWh in SEK for Sweden, Denmark and Norway collected over the last 30 days.

The graph was generated at

Also I bought two books today that I have thought about for some time, Mastering regular expressions by Jeffrey E. F. Friedl and C++ Gotchas by Stephen C. Dewhurst. I think I will be able to pickup some new ideas from these. From what I have heard they should be good.

New bulbs

So I finally decided to change the lightbulbs in my aquarium-lamp. According to the book you should change bulbs once a year, but I have now waited for about 5 years, partly because the bulbs are so expensive and partly because I do not have any corals (except for 2 dead ones) or other inhabitants that are very much in need of a correct light temperature or intensity. For two 250 W 13000K bulbs I paid 1750 NOK (~210€ ). Hopefully the higher (more blue) light temperature will make corals feel better than they did the last time I tried and hopefully the algae will like it less. The previous bulbs were 10000K. For reference the color temperature of a candle flame is about 2000K, the sun about 5000K and the sky 8000-10000K. So 13000K is pretty blue. By the initial definition it is the color that a block of carbon would glow with if you heated it up to 13000K (12727 ℃ ).

Changing the bulbs took me about an hour, becase you need a ladder to reach the roof, then you must make sure that you are steady on your hands so you do not drop the entire lamp into the saltwater. By yourself it’s a small challange, but it all went fine.

By the way note that I use real unicode chars for both Kelvin and Celcius. K is different from K, and ℃ is different from °C =) And by another way it’s not called a degree centigrade it’s called a degree Celcius since 1948!