# 2
#
"""
A fair split? Number partitioning
Duty: To divide a list of n integers into two sublists with equal sums.
More vividly, divide n players with skills S[i] into two teams of equal total
skill.
"""
#
import scipy
import pylab
import RandomArray
#
# Four sample lists to test
S1 = scipy.array([10,13,23,6,20])
S2 = scipy.array([6,4,9,14,12,3,15,15])
S3 = scipy.array([93,58,141,209,179,48,225,228])
S4 = scipy.array([2474,1129,1388,3752,821,2082,201,739])
#
def AllTeams(n):
"""
Returns a scipy array of all 2^n vectors of length n composed of +-1,
giving the possible teams for n total players (so AllTeams(2) should
return [[-1,-1],[-1,1],[1,-1],[1,1]]).
One method is to build an n x 2^n array, with ij entry j/(2**i) mod 2
(x%2 is x mod 2), and then multiply the array by two and subtract one.
(If you can do this entirely with scipy arrays, it'll be significantly
faster: you'll need to use scipy.arange to 2**n, scipy.mod, and
scipy.transpose (C. R. Myers, private communication). The speedup,
though, won't be important for the sizes in this exercise.)
"""
pass
#
# Build allTeamsArray[n] = AllTeams(n) for n from zero to twelve, so we don't
# need to rebuild the team arrays for each new problem instance.
# (allTeamsArray[0] will look weird.)
# allTeamsArray = ...
#
def ExhaustivePartition(S):
"""
Returns the minimum size team, given players S. This is nicely done by
taking scipy.dot of allTeamsArray[len(S)] with S, and then using
abs and min.
"""
pass
#
def MakeRandomPartitionProblem(N, M):
"""
Returns a random series of N integers in the range 1 < p < 2**M, guaranteed
to sum to an even number. Use RandomArray.randint to generate a length N
vector S of the appropriate range. While sum(S) mod 2 is not zero,
re-generate S.
"""
pass
#
def pPerf(N, M, trials=100):
"""
Returns the fraction of perfect partitions among "trials" runs of
N variables of M bits each.
"""
pass
#
def Plot_pPerf_versus_kappa(Ns=[3,5,7,9], trials=100):
"""
Plots pPerf(N,M,trials) versus kappa=M/N for M in the range 1-2*N
(For N in Ns, sets up empty lists of pPerfs and kappas; for M in
the range appends float(M)/float(N) to kappas and pPerf(...) to pPerfs;
then pylab.plot(kappas, pPerfs) and pylab.show().)
"""
pass
#
def Plot_pPerf_Scaling():
"""
Plots the scaling function, for x from -6, 6, in steps of 0.01.
(You'll need to use scipy.exp, scipy.sqrt, and scipy.pi. Use linewidth=3
to distinguish the scaling curve.)
"""
pass
#
def Plot_pPerf_versus_x(Ns=[3,5,7,9], trials=100):
"""
Plots pPerf(N,M,trials) versus x for M in the range 1-2*N,
and then calls Plot_pPerf_Scaling to generate the theory curve.
"""
pass
#
# Copyright (C) Cornell University
# All rights reserved.
# Apache License, Version 2.0