'===========================================================================
' Subject: CALCULATE # OF COMBINATIONS       Date: 01-05-97 (17:00)       
' Author:  Marek Piotrowski                  Code: QB, QBasic, PDS        
' Origin:  ao487@freenet.toronto.on.ca     Packet: ALGOR.ABC
'===========================================================================
' Did you ever try to compare what are your odds in different lotteries?
'
' This algorithm simplifies the task.
'
'
'    This is the formula for number of k-element combinations out of
'    n elements:
'
'                n!
'     X  = -----------------
'            (n - k)! * k!
'
'
'      Where n - total number of elements
'            k - number of elements in one combination
'            n! = 1 * 2 * , , * n      factorial of n
'            k! = 1 * 2 * , , * k      factorial of k
'            X - number of possible k-element combinations
'

DEFINT D, K, N, R
DEFDBL X
DEFLNG Y

' I am going to comment this algorithm assuming number of elements n=49
' and 6-element combinations k=6.


INPUT "Enter total number of elements            :"; n
INPUT "Enter number of elements in a combination :"; k
PRINT

' After entering n=49 and k=6 our formula looks like that:

'                49!             43! * 44 * 45 * 46 * 47 * 48 * 49
'     X  = ----------------- = --------------------------------------
'            (49 - 6)! * 6!        (43)! * 1 * 2 * 3 * 4 * 5 * 6
'
' Since n and k are already known I create two integer arrays: Numerator
' and Denominator. These arrays will hold all the factors of the fraction.
' Both arrays are k=6 element arrays.

DIM Numerator(k) AS INTEGER
DIM Denominator(k) AS INTEGER

' Let fill the arrays with proper values.
' Numerator array holds numbers 44 to 49. Denominator array holds numbers
' 1 to 6

Bracket = n - k

FOR i = 1 TO k
  Numerator(i) = Bracket + i
  Denominator(i) = i
NEXT i

' Now our fraction looks as follows
'
'            44 * 45 * 46 * 47 * 48 * 49
'     X =    ----------------------------
'               1 * 2 * 3 * 4 * 5 * 6
'
' and obviously can be simplified.                44                      22        45                     15
' For instance ----- can be reduced to ----- ,   ---- can be reduced to -----
'                2                       1         3                      1
'
' and so on. Following lines take care of most possible cases like
'
'  6     3          3     1          51     3
' --- = ---    or  --- = ---    or  ---- = ---
'  4     2          9     3          34     2

FOR i = 1 TO k
  FOR j = 1 TO k
      IF Denominator(i) > 1 AND Numerator(j) > 1 THEN
        IF Numerator(j) MOD Denominator(i) = 0 THEN
          Numerator(j) = Numerator(j) \ Denominator(i)
          Denominator(i) = Denominator(i) \ Denominator(i)
        END IF
        IF Denominator(i) MOD Numerator(j) = 0 THEN
          Denominator(i) = Denominator(i) \ Numerator(j)
          Numerator(j) = Numerator(j) \ Numerator(j)
        END IF
        FOR z = 2 TO 7
          IF Denominator(i) MOD z = 0 AND Numerator(j) MOD z = 0 THEN
            Denominator(i) = Denominator(i) \ z
            Numerator(j) = Numerator(j) \ z
          END IF
        NEXT z

      END IF


  NEXT j
NEXT i

' By now most of Denominator array elements should be equal 1.
' Our fraction looks like that:
'
'            22 *  3 * 46 * 47 *  2 * 49
'     X =    ----------------------------
'               1 * 1 * 1 * 1 * 1 * 1
'
' Final result is a quotient of products.
'
X = 1
Y = 1

FOR i = 1 TO k
  X = X * Numerator(i)      'Calculating numerator product
  Y = Y * Denominator(i)    'Calculating denominator product
NEXT i

X = X / Y                   'Dividing numerator by denominator

PRINT "Number of"; k; "element combinations out of"; n; "numbers is"; X