Fighting with computers

Computers are not always friendly.

Sunday, September 21, 2008

Sterling numbers of the second order


I am sure once in a while you may have faced the problem of distributing n elements into k different groups. It does not seem rocket science but, do you know in how many different ways it can be done? Of course it is not a new problem a all, and here is where the Stirling numbers (of the second kind) come in handy: they tell you the ways of dividing n elements into k groups.

For the Code Jam problem "Square Fields" large dataset the numbers may seem discouraging as the number of alternatives for 15 elements are:
S2(15,1)=1
S2(15,2)=16383
S2(15,3)=2375101
S2(15,4)=42355950
S2(15,5)=210766920
S2(15,6)=420693273
S2(15,7)=408741333
S2(15,8)=216627840
S2(15,9)=67128490
S2(15,10)=12662650
S2(15,11)=1479478
S2(15,12)=106470
S2(15,13)=4550
S2(15,14)=105

But for the small dataset combinations are just a few after all:
S2(7,1)=1
S2(7,2)=63
S2(7,3)=301
S2(7,4)=350
S2(7,5)=140
S2(7,6)=21

So brute force would have worked nicely for the small dataset case but not so for the large one.

0 Comments:

Post a Comment

<< Home