#! /usr/bin/env python
#
def binom ( n, k ):

#*****************************************************************************80
#
## BINOM computes the binomial coefficient.
#
#  Discussion:
#
#    This is ACM algorithm 160 translated.
#
#    It calculates the number of combinations of N things taken K at a time.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    Bill Buckles, Matthew Lybanon
#
#  Reference:
#
#    Bill Buckles, Matthew Lybanon,
#    Algorithm 515: Generation of a Vector from the Lexicographical Index,
#    ACM Transactions on Mathematical Software,
#    Volume 3, Number 2, June 1977, pages 180-182.
#
#  Parameters:
#
#    Input, integer N, K, the parameters for the binomial 
#    coefficient.
#
#    Output, integer VALUE, the binomial coefficient.
#

#
#  Force the input arguments to be integers.
#
  n = int ( n )
  k = int ( k )

  k1 = k
  p = n - k1

  if ( k1 < p ):
    p = k1
    k1 = n - p

  if ( p == 0 ):
    r = 1
  else:
    r = k1 + 1

  for i in range ( 2, p + 1 ):
    r = ( r * ( k1 + i ) ) // i

  value = int ( r )

  return value

def comb ( n, p, l ):

#*****************************************************************************80
#
## COMB selects a subset of order P from a set of order N.
#
#  Discussion:
#
#    This subroutine finds the combination set of N things taken
#    P at a time for a given lexicographic index.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    Bill Buckles, Matthew Lybanon
#
#  Reference:
#
#    Bill Buckles, Matthew Lybanon,
#    Algorithm 515: Generation of a Vector from the Lexicographical Index,
#    ACM Transactions on Mathematical Software,
#    Volume 3, Number 2, June 1977, pages 180-182.
#
#  Parameters:
#
#    Input, integer N, the number of things in the set.
#
#    Input, integer P, the number of things in each combination.
#    0 < P < N.
#
#    Input, integer L, the lexicographic index of the 
#    desired combination.  1 <= L <= choose(N,P).
#
#    Output, integer C(P), the combination set.
#
  import numpy as np

  c = np.zeros ( p )
#
#  Special case: P = 1
#
  if ( p == 1 ):
    c[0] = l
    return c
#
#  Initialize lower bound index.
#
  k = 0
#
#  Select elements in ascending order.
#
  p1 = p - 1
  c[0] = 0

  for i in range ( 1, p1 + 1 ):
#
#  Update lower bound as the previously selected element.
#
    if ( 1 < i ):
      c[i-1] = c[i-2]
#
#  Check validity of each entry.
#
    while ( True ):

      c[i-1] = c[i-1] + 1
      r = binom ( n - c[i-1], p - i )
      k = k + r

      if ( l <= k ):
        break

    k = k - r

  c[p-1] = c[p1-1] + l - k

  return c

def comb_test01 ( ):

#*****************************************************************************80
#
## COMB_TEST01 tests COMB by generating all 3-subsets of a 5 set.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    John Burkardt
#
  import platform
  from i4_choose_check import i4_choose_check

  n = 5
  k = 3
  lmax = binom ( n, k )

  print ( '' )
  print ( 'COMB_TEST01' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Generate all K-subsets of an N set.' )
  print ( '  K = %d' % ( k ) )
  print ( '  N = %d' % ( n ) )
  print ( '  LMAX = %d' % ( lmax ) )

  if ( not i4_choose_check ( n, k ) ):
    print ( '' )
    print ( 'COMB_TEST01 - Warning!' )
    print ( '  The binomial coefficient cannot be' )
    print ( '  computed in integer arithmetic for' )
    print ( '  this choice of parameters.' )
    return

  print ( '' )

  for l in range ( 1, lmax + 1 ):
    c = comb ( n, k, l )
    print ( '  %6d:  ' % ( l ) ),
    for i in range ( 0, k ):
      print ( '  %6d' % ( c[i] ) ),
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'COMB_TEST01_TEST:' )
  print ( '  Normal end of execution.' )
  return

def comb_test02 ( ):

#*****************************************************************************80
#
## COMB_TEST02 tests COMB by generating 10 random 3-subsets of a 10 set.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    John Burkardt
#
  import platform
  from i4_choose_check import i4_choose_check
  from i4_uniform_ab import i4_uniform_ab

  n = 5
  k = 3
  lmax = binom ( n, k )

  print ( '' )
  print ( 'COMB_TEST02' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Generate all K-subsets of an N set.' )
  print ( '  K = %d' % ( k ) )
  print ( '  N = %d' % ( n ) )
  print ( '  LMAX = %d' % ( lmax ) )

  if ( not i4_choose_check ( n, k ) ):
    print ( '' )
    print ( 'COMB_TEST02 - Warning!' )
    print ( '  The binomial coefficient cannot be' )
    print ( '  computed in integer arithmetic for' )
    print ( '  this choice of parameters.' )
    return

  print ( '' )

  seed = 123456789

  for i in range ( 0, 10 ):
    l, seed = i4_uniform_ab ( 1, lmax, seed )
    c = comb ( n, k, l )
    print ( '  %6d:  ' % ( l ) ),
    for i in range ( 0, k ):
      print ( '  %6d' % ( c[i] ) ),
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'COMB_TEST02_TEST:' )
  print ( '  Normal end of execution.' )
  return

def comb_test03 ( ):

#*****************************************************************************80
#
## COMB_TEST03 tests COMB by generating 10 random 3-subsets of a 25 set.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    John Burkardt
#
  import platform
  from i4_choose_check import i4_choose_check
  from i4_uniform_ab import i4_uniform_ab

  n = 25
  k = 3
  lmax = binom ( n, k )

  print ( '' )
  print ( 'COMB_TEST03' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Generate 10 random K-subsets of an N set.' )
  print ( '  K = %d' % ( k ) )
  print ( '  N = %d' % ( n ) )
  print ( '  LMAX = %d' % ( lmax ) )

  if ( not i4_choose_check ( n, k ) ):
    print ( '' )
    print ( 'COMB_TEST03 - Warning!' )
    print ( '  The binomial coefficient cannot be' )
    print ( '  computed in integer arithmetic for' )
    print ( '  this choice of parameters.' )
    return

  print ( '' )

  seed = 123456789

  for i in range ( 0, 10 ):
    l, seed = i4_uniform_ab ( 1, lmax, seed )
    c = comb ( n, k, l )
    print ( '  %6d:  ' % ( l ) ),
    for i in range ( 0, k ):
      print ( '  %6d' % ( c[i] ) ),
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'COMB_TEST03_TEST:' )
  print ( '  Normal end of execution.' )
  return
 
def comb_test04 ( ):

#*****************************************************************************80
#
## COMB_TEST04 tests COMB by generating 10 random 3-subsets of a 100 set.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    John Burkardt
#
  import platform
  from i4_choose_check import i4_choose_check
  from i4_uniform_ab import i4_uniform_ab

  n = 100
  k = 3
  lmax = binom ( n, k )

  print ( '' )
  print ( 'COMB_TEST04' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Generate 10 random K-subsets of an N set.' )
  print ( '  K = %d' % ( k ) )
  print ( '  N = %d' % ( n ) )
  print ( '  LMAX = %d' % ( lmax ) )

  if ( not i4_choose_check ( n, k ) ):
    print ( '' )
    print ( 'COMB_TEST04 - Warning!' )
    print ( '  The binomial coefficient cannot be' )
    print ( '  computed in integer arithmetic for' )
    print ( '  this choice of parameters.' )
    return

  print ( '' )

  seed = 123456789

  for i in range ( 0, 10 ):
    l, seed = i4_uniform_ab ( 1, lmax, seed )
    c = comb ( n, k, l )
    print ( '  %6d:  ' % ( l ) ),
    for i in range ( 0, k ):
      print ( '  %6d' % ( c[i] ) ),
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'COMB_TEST04_TEST:' )
  print ( '  Normal end of execution.' )
  return

def comb_test05 ( ):

#*****************************************************************************80
#
## COMB_TEST05 tests COMB by generating 10 random 10-subsets of a 100 set.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    31 March 2016
#
#  Author:
#
#    John Burkardt
#
  import platform
  from i4_choose_check import i4_choose_check
  from i4_uniform_ab import i4_uniform_ab

  n = 100
  k = 10
  lmax = binom ( n, k )

  print ( '' )
  print ( 'COMB_TEST05' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Generate 10 random K-subsets of an N set.' )
  print ( '  K = %d' % ( k ) )
  print ( '  N = %d' % ( n ) )
  print ( '  LMAX = %d' % ( lmax ) )
  print ( '' )
  print ( '  Note that this function is already' )
  print ( '  failing because LMAX is negative.' )
  print ( '  The combinatorial coefficient C(100,10)' )
  print ( '  is too large to store in an integer.' )
  print ( '' )
  print ( '  Although the program continues to give' )
  print ( '  results, they cannot be relied on!' )

  if ( not i4_choose_check ( n, k ) ):
    print ( '' )
    print ( 'COMB_TEST05 - Warning!' )
    print ( '  The binomial coefficient cannot be' )
    print ( '  computed in integer arithmetic for' )
    print ( '  this choice of parameters.' )
    return

  print ( '' )

  seed = 123456789

  for i in range ( 0, 10 ):
    l, seed = i4_uniform_ab ( 1, lmax, seed )
    c = comb ( n, k, l )
    print ( '  %6d:  ' % ( l ) ),
    for i in range ( 0, k ):
      print ( '  %6d' % ( c[i] ) ),
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'COMB_TEST05_TEST:' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  comb_test01 ( )
  comb_test02 ( )
  comb_test03 ( )
  comb_test04 ( )
  comb_test05 ( )
  timestamp ( )