Stirling Number Generation using Python (Code + Examples)

Posted: January 21, 2013 in Programming, Python
Tags: , ,

This is a guide on how we can generate Stirling numbers using Python programming language.

Stirling Number S(n,k) :

A Stirling Number of the second kind, S(n, k), is the number of ways of splitting “n” items in “k” non-empty sets.

The formula used for calculating Stirling Number is:

S(n, k) = k* S(n-1, k) + S(n-1, k-1)

 
Example 1:

If you want to split a group of 3 items into 2 groups where {A, B, C} are the elements, and {Group 1} and {Group 2} are two groups, you can split them are follows:

{Group 1}                    {Group 2}

A, B                                    C

A                                        B, C

B                                        A, C

So, the number of ways of splitting 3 items into 2 groups = 3.

Therefore,  the Stirling number , S(3, 2) = 3

Example 2:

If you want to split a group of 5 elements into 2 groups where {A,B,C,D,E} are the items and {Group 1} and {Group 2} are two groups, it can be done in a total of 7 ways. So,

S(4, 2) = 7

Code:
This is the code that I have written to generate Stirling Numbers.

# Stirling Algorithm
# Cod3d by EXTR3ME
# https://extr3metech.wordpress.com

def stirling(n,k):
    n1=n
    k1=k
    if n<=0:
        return 1
    
    elif k<=0:
        return 0
    
    elif (n==0 and k==0):
        return -1
    
    elif n!=0 and n==k:
        return 1
    
    elif n<k:
        return 0

    else:
        temp1=stirling(n1-1,k1)
        temp1=k1*temp1
        return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1)

print   stirling(1,1)
# Output = 1

print stirling(5,2)
# Output  = 15

print stirling(5,3)
# Output  = 25

print stirling(5,4)
# Output  = 10

print stirling(5,5)
# Output  = 1

print stirling(20,15)
# Output  =  452329200

#print stirling(30,10)

# End of Code

Note: When the values of n and k are large , it will take longer to calculate. For example, I have hashed out print stirling(30, 10) , as it can take a while to calculate. You can always unhash it and test how long it takes to calculate in your computer. Feel free to leave any comments or feedback.

Hope this helps. You can always subscribe to my blog to get more updates! Happy Coding!

ΞXΤЯ3МΞ

Comments
  1. Mark Andrews says:

    Hi – I think there may be as easy way to speed it up. As this function is defined recursively, the function call make two functions calls which then make two and so on. The slowing is exponential. Here are some example times:

    stirling(5,5) = 1. Calculated in 0.00000215 secs.
    stirling(10,5) = 42525. Calculated in 0.00313711 secs.
    stirling(15,10) = 12662650. Calculated in 0.04619098 secs.
    stirling(20,15) = 452329200. Calculated in 0.25143695 secs.
    stirling(25,20) = 6220194750. Calculated in 0.90307903 secs.
    stirling(30,25) = 49402080000. Calculated in 2.50413704 secs.
    stirling(30,24) = 2157580085700. Calculated in 18.38733101 secs.
    stirling(30,23) = 71823880393200. Calculated in 121.74350500 secs.

    You can create a decorator is cache or “memoize” the result of any function call, and the speed up is dramatic:

    memoized stirling(5,5) = 1. Calculated in 0.00000286 secs.
    memoized stirling(10,5) = 42525. Calculated in 0.00005388 secs.
    memoized stirling(15,10) = 12662650. Calculated in 0.00004387 secs.
    memoized stirling(20,15) = 452329200. Calculated in 0.00005889 secs.
    memoized stirling(25,20) = 6220194750. Calculated in 0.00005698 secs.
    memoized stirling(30,25) = 49402080000. Calculated in 0.00004697 secs.
    memoized stirling(30,24) = 2157580085700. Calculated in 0.00005603 secs.
    memoized stirling(30,23) = 71823880393200. Calculated in 0.00003886 secs.

    The way I did this was to make a decorator function:
    def memoize(func):
    S = {}
    def wrappingfunction(*args):
    if args not in S:
    S[args] = func(*args)
    return S[args]
    return wrappingfunction

    and then did

    @memoize
    def stirling(n,k):

    I have not tried it with other functions, but I think that the form the memoize decorator above is probably generally enough to be used in many different situations.

    best wishes,
    -Mark

    • ΞXΤЯ3МΞ says:

      Hi Mark, thanks a lot for visiting my blog and taking your time and effort to post the optimized code. I just checked it out and the performance is a whole lot better using the Memoization technique. I will be creating a post on Stirling Number Generation and others using this technique in the future. And once again, thank you for visiting my blog!🙂

      ΞXΤЯ3МΞ

  2. Hobs says:

    The follow test gives an incorrect answer (according to http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind):

    >>> stirling(4, 2)
    7

    (should be 11)

  3. csl says:

    Looking at the explicit formula from https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind you can also make it much faster by not doing it recursively:

    from math import factorial

    def binom(a,b):
    return factorial(a) / (factorial(b)*factorial(a-b))

    def stirling_fast(n,k):
    if n<=0 or n!=0 and n==k:
    return 1
    elif k<=0 or n<k:
    return 0
    elif n==0 and k==0:
    return -1
    else:
    s = sum((-1)**(k-j)*binom(k,j)*j**n for j in range(k+1))
    return s / factorial(k)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s