Combinations Sub: choose(n,k)

Discussion in 'Code Samples & Tips' started by Stellaferox, Feb 21, 2008.

  1. Stellaferox

    Stellaferox Active Member Licensed User

    Hi,

    I developed a sub for computinf the amout of combinations, given a population N, choose subset K (notation: choose(n,k).
    Example: how many combinations are possible for 7 cards from 52?
    choose(52,7). To compute n!/((n-k)!*k!)
    Because this creates an overflow for relatively small numbers I created an alternative and really fast routine.

    Code:
    Sub Choose(nn,kk)
       
    ' effficient Choose method implementation

       
    If (nn<0OR (kk<0Then Msgbox("Invalid negative parameter in Choose()..")
       
    If (nn<kk) Then Return 0
       
    If (nn=kk) Then Return 1

       delta = 
    0
       imax = 
    0

       
    If (kk < (nn-kk)) Then 'choose(100,3)
          delta = nn-kk
          imax = kk
       
    Else 'choose(100,97)
          delta = kk
          imax = nn-kk
       
    End If

       ans = delta+
    1
       
    For i = 2 To imax
          ans = (ans * (delta + i))/i
       
    Next
       
    Return ans
    End Sub
    I am building an application for displaying and storing all possible combinations. When ready I will publish.

    Have fun

    Marc
     
  2. derez

    derez Expert Licensed User

  3. Stellaferox

    Stellaferox Active Member Licensed User

    Hi David,

    Yes I have and I find it very useful.
    Thank you for that, by the way...
    However I needed an application for my main application to find a next combination without using recursive programming.
    I found it at:
    http://msdn.microsoft.com/msdnmag/issues/04/07/TestRun/default.aspx
    I translated the code a bit and added some for my own code. Now I can use any combination and find its immediate successor or predecessor.
    Marc
     
Loading...