#! /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 ( )