#! /usr/bin/env python3
#
def partition_brute ( n, w ):

#*****************************************************************************80
#
## partition_brute() approaches the partition problem using brute force.
#
#  Discussion:
#
#    We are given a set of N integers W.
#
#    We seek to partition W into subsets W0 and W1, such that the subsets
#    have equal sums.
#
#    The "discrepancy" is the absolute value of the difference between the
#    two sums, and will be zero if we have solved the problem.
#
#    For a given set of integers, there may be zero, one, or many solutions.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer N, the size of the set.
#
#    integer W(N), the integers.
#
#  Output:
#
#    bool C(N), indicates the proposed solution.
#    C(I) is True or False if weight I is or is not in the left set of the
#    partition.
#
#    integer DISCREPANCY, the discrepancy.
#
  import numpy as np

  w_sum = np.sum ( w )

  c = np.zeros ( n, dtype = np.int32 )
  discrepancy = w_sum

  d = np.zeros ( n, dtype = np.int32 )

  rank = -1

  while ( True ):

    d, rank = subset_next ( n, d, rank )

    if ( rank == -1 ):
      break

    p_sum = 0
    for i in range ( 0, n ):
      if ( d[i] ):
        p_sum = p_sum + w[i]

    d_discrepancy = abs ( w_sum - 2 * p_sum )

    if ( d_discrepancy < discrepancy ):
      discrepancy = d_discrepancy
      for i in range ( 0, n ):
        c[i] = d[i]

    if ( discrepancy == 0 ):
      break

  return c, discrepancy

def partition_brute_test ( n, w ):

#*****************************************************************************80
#
## partition_brute_test() tests partition_brute().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer N, the number of weights.
#
#    integer W(N), a set of weights.
#
  import platform

  print ( '' )
  print ( 'partition_brute_test:' )
  print ( '  partition_brute seeks a balanced partition using brute force.' )
  print ( '  Partition a set of N integers W so that the subsets' )
  print ( '  have equal sums.' )

  c, discrepancy = partition_brute ( n, w )

  print ( '' )
  print ( '     I        W0        W1' )
  print ( '' )
  w0_sum = 0
  w1_sum = 0
  for i in range ( 0, n ):
    if ( c[i] ):
      w0_sum = w0_sum + w[i]
      print ( '  %4d  %8d' % ( i, w[i] ) )
    else:
      w1_sum = w1_sum + w[i]
      print ( '  %4d            %8d' % ( i, w[i] ) )

  print ( '        --------  --------' )
  print ( '        %8d  %8d' % ( w0_sum, w1_sum ) )
  print ( '' )
  print ( '  Discrepancy = %d' % ( discrepancy ) )
#
#  Terminate.
#
  print ( '' )
  print ( 'partition_brute_test:' )
  print ( '  Normal end of execution.' )
  return

def partition_brute_tests ( ):

#*****************************************************************************80
#
## partition_brute_tests() tests partition_brute_test().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'partition_brute_tests:' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  partition_brute_test calls partition_brute with a particular.' )
  print ( '  set of weights.' )

  for test in range ( 0, 5 ):

    if ( test == 0 ):
      n = 5
      w = np.array ( [ 19, 17, 13, 9, 6 ] )
    elif ( test == 1 ):
      n = 9
      w = np.array ( [ 484, 114, 205, 288, 506, 503, 201, 127, 410 ] )
    elif ( test == 2 ):
      n = 10
      w = np.array ( [ 771, 121, 281, 854, 885, 734, 486, 1003, 83, 62 ] )
    elif ( test == 3 ):
      n = 10
      w = np.array ( [ 2, 10, 3, 8, 5, 7, 9, 5, 3, 2 ] )
    elif ( test == 4 ):
      n = 9
      w = np.array ( [ 3, 4, 3, 1, 3, 2, 3, 2, 1 ] )

    partition_brute_test ( n, w )
#
#  Terminate.
#
  print ( '' )
  print ( 'partition_brute_tests:' )
  print ( '  Normal end of execution.' )
  return

def partition_count ( n, w ):

#*****************************************************************************80
#
## partition_count() counts the solutions to a partition problem.
#
#  Discussion:
#
#    We are given a set of N integers W.
#
#    We seek to partition W into subsets W0 and W1, such that the subsets
#    have equal sums.
#
#    The "discrepancy" is the absolute value of the difference between the
#    two sums, and will be zero if we have solved the problem.
#
#    For a given set of integers, there may be zero, one, or many solutions.
#
#    In the case where the weights are distinct, the count returned by this
#    function may be regarded as twice as big as it should be, since the
#    partition (W0,W1) is counted a second time as (W1,W0).  A more serious
#    overcount can occur if the set W contains duplicate elements - in the
#    extreme case, W might be entirely 1's, in which case there is really
#    only one (interesting) solution, but this function will count many.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    12 May 2012
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer N, the size of the set.
#
#    integer W(N), the integers.
#
#  Output:
#
#    integer COUNT, the number of solutions.
#
  import numpy as np

  w_sum = np.sum ( w )

  c = np.zeros ( n, dtype = np.bool )
  rank = -1
  count = 0

  while ( True ):

    c, rank = subset_next ( n, c, rank )

    if ( rank == -1 ):
      break

    p_sum = 0
    for i in range ( 0, n ):
      if ( c[i] ):
        p_sum = p_sum + w[i]

    discrepancy = abs ( w_sum - 2 * p_sum )

    if ( discrepancy == 0 ):
      count = count + 1

  return count

def partition_count_test ( n, w ):

#*****************************************************************************80
#
## partition_count_test() tests partition_count().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer N, the number of weights.
#
#    integer W(N), a set of weights.
#
  print ( '' )
  print ( 'partition_count_test:' )
  print ( '  partition_count counts the number of exact solutions' )
  print ( '  of the partition problem.' )

  count = partition_count ( n, w )

  print ( '' )
  print ( '     I        W' )
  print ( '' )
  for i in range ( 0, n ):
    print ( '  %4d  %8d' % ( i, w[i] ) )
  print ( '' )
  print ( '  Number of solutions = %d' % ( count ) )
#
#  Terminate.
#
  print ( '' )
  print ( 'partition_count_test:' )
  print ( '  Normal end of execution.' )
  return

def partition_count_tests ( ):

#*****************************************************************************80
#
## partition_count_tests() tests partition_count_test().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'partition_count_tests:' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  partition_count_test calls partition_count with a particular' )
  print ( '  set of weights.' )

  for test in range ( 0, 5 ):

    if ( test == 0 ):
      n = 5
      w = np.array ( [ 19, 17, 13, 9, 6 ] )
    elif ( test == 1 ):
      n = 9
      w = np.array ( [ 484, 114, 205, 288, 506, 503, 201, 127, 410 ] )
    elif ( test == 2 ):
      n = 10
      w = np.array ( [ 771, 121, 281, 854, 885, 734, 486, 1003, 83, 62 ] )
    elif ( test == 3 ):
      n = 10
      w = np.array ( [ 2, 10, 3, 8, 5, 7, 9, 5, 3, 2 ] )
    elif ( test == 4 ):
      n = 9
      w = np.array ( [ 3, 4, 3, 1, 3, 2, 3, 2, 1 ] )

    partition_count_test ( n, w )
#
#  Terminate.
#
  print ( '' )
  print ( 'partition_count_tests:' )
  print ( '  Normal end of execution.' )
  return

def partition_problem_test ( ):

#*****************************************************************************80
#
## partition_problem_test() tests the partition_problem library.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
  import platform

  print ( '' )
  print ( 'partition_problem_test:' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Test the partition_problem library.' )

  partition_brute_tests ( )
  partition_count_tests ( )
  subset_next_test ( )
#
#  Terminate.
#
  print ( '' )
  print ( 'partition_problem_test:' )
  print ( '  Normal end of execution.' )
  return

def subset_next ( n, t, rank ):

#*****************************************************************************80
#
## subset_next() computes the subset lexicographic successor.
#
#  Discussion:
#
#    This is a lightly modified version of "subset_lex_successor()" from COMBO.
#
#  Example:
#
#    On initial call, N is 5 and the input value of RANK is -1.
#    Then here are the successive outputs from the program:
#
#   Rank   T1   T2   T3   T4   T5
#   ----   --   --   --   --   --
#      0    0    0    0    0    0
#      1    0    0    0    0    1
#      2    0    0    0    1    0
#      3    0    0    0    1    1
#     ..   ..   ..   ..   ..   ..
#     30    1    1    1    1    0
#     31    1    1    1    1    1
#     -1    0    0    0    0    0  <-- Reached end of cycle.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    09 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Input:
#
#    integer N, the number of elements in the master set.
#    N must be positive.
#
#    bool T(N), describes a subset.  T(I) is False if
#    the I-th element of the master set is not in the subset, and is
#    True if the I-th element is part of the subset.
#
#    integer RANK, the rank.
#    If RANK = -1 on then the routine understands that this is
#    the first call, and that the user wishes the routine to supply
#    the first element in the ordering, which has RANK = 0.
#
#  Output:
#
#    bool T(N), describes the next subset. 
#
#    integer RANK, the rank.
#    In general, the input value of RANK is increased by 1 for output,
#    unless the very last element of the ordering was in which
#    case the output value of RANK is -1.
#

#
#  Return the first element.
#
  if ( rank == -1 ):
    rank = 0
    return t, rank

  for i in range ( n - 1, -1, -1 ):

    if ( not t[i] ):
      t[i] = True
      rank = rank + 1
      return t, rank

    t[i] = False

  rank = -1

  return t, rank

def subset_next_test ( ):

#*****************************************************************************80
#
## subset_next_test() tests subset_next().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    10 November 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'subset_next_test' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  subset_next generates all subsets of an N set.' )

  print ( '' )
  n = 5
  t = np.zeros ( n, dtype = np.bool )
  rank = -1
  
  while ( True ):
 
    t, rank = subset_next ( n, t, rank )
 
    if ( rank == -1 ):
      break

    k = 0

    for i in range ( 0, n ):

      if ( t[i] ):
        k = k + 1
        print ( '  %d' % ( i ) ),

    if ( k == 0 ):
      print ( '  (empty set)' ),

    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'subset_next_test:' )
  print ( '  Normal end of execution.' )
  return

def timestamp ( ):

#*****************************************************************************80
#
## timestamp() prints the date as a timestamp.
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    06 April 2013
#
#  Author:
#
#    John Burkardt
#
  import time

  t = time.time ( )
  print ( time.ctime ( t ) )

  return None

if ( __name__ == '__main__' ):
  timestamp ( )
  partition_problem_test ( )
  timestamp ( )