#! /usr/bin/env python
#
def i4_choose ( n, k ):
#*****************************************************************************80
#
## I4_CHOOSE computes the binomial coefficient C(N,K) as an I4.
#
# Discussion:
#
# The value is calculated in such a way as to avoid overflow and
# roundoff. The calculation is done in integer arithmetic.
#
# The formula used is:
#
# C(N,K) = N! / ( K! * (N-K)! )
#
# Licensing:
#
# This code is distributed under the GNU LGPL license.
#
# Modified:
#
# 30 October 2014
#
# Author:
#
# John Burkardt
#
# Reference:
#
# ML Wolfson, HV Wright,
# Algorithm 160:
# Combinatorial of M Things Taken N at a Time,
# Communications of the ACM,
# Volume 6, Number 4, April 1963, page 161.
#
# Parameters:
#
# Input, integer N, K, are the values of N and K.
#
# Output, integer VALUE, the number of combinations of N
# things taken K at a time.
#
mn = min ( k, n - k )
mx = max ( k, n - k )
if ( mn < 0 ):
value = 0
elif ( mn == 0 ):
value = 1
else:
value = mx + 1
for i in range ( 2, mn + 1 ):
value = ( value * ( mx + i ) ) / i
return value
def i4_choose_test ( ):
#*****************************************************************************80
#
## I4_CHOOSE_TEST tests I4_CHOOSE.
#
# Licensing:
#
# This code is distributed under the GNU LGPL license.
#
# Modified:
#
# 27 October 2014
#
# Author:
#
# John Burkardt
#
import platform
print ( '' )
print ( 'I4_CHOOSE_TEST' )
print ( ' Python version: %s' % ( platform.python_version ( ) ) )
print ( ' I4_CHOOSE evaluates C(N,K).' )
print ( '' )
print ( ' N K CNK' )
for n in range ( 0, 5 ):
print ( '' )
for k in range ( 0, n + 1 ):
cnk = i4_choose ( n, k )
print ( ' %6d %6d %6d' % ( n, k, cnk ) )
#
# Terminate.
#
print ( '' )
print ( 'I4_CHOOSE_TEST:' )
print ( ' Normal end of execution.' )
return
if ( __name__ == '__main__' ):
from timestamp import timestamp
timestamp ( )
i4_choose_test ( )
timestamp ( )