049: Number Partitioning

$ 
$ Set partition problem in Essence'
$
$
$ Problem formulation from
$   http://www.koalog.com/resources/samples/PartitionProblem.java.html
$ """
$  This is a partition problem.
$  Given the set S = {1, 2, ..., n}, 
$  it consists in finding two sets A and B such that:
$  

$  
A U B = S,
$  
|A| = |B|,
$  
sum(A) = sum(B),
$  
sum_squares(A) = sum_squares(B).
$  
$"""
$
$ This Essence' model was created by Hakan Kjellerstrand, hakank@gmail.com .
$ See also my Tailor/Essence' page: http://www.hakank.org/savile_row/ .
$

$ Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

language ESSENCE' 1.0

$ For num_sets n must be a multiple of 4 for this to work.
$ And - of course - num_sets must be a multiple of n.

letting n be 16
letting num_sets be 2

$ one solution
$ 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
$ 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2;
$ ->
$ 1: {1,2,7,8,11,12,13,14},
$ 2: {3,4,5,9,10,15,16}


$ Essence' don't support sets so we represent the sets 
$ simply as a value in the a array.
find a: matrix indexed by [int(1..n)] of int(1..num_sets)

find sums: matrix indexed by [int(1..num_sets)] of int(0..n*n)
find sums_squared: matrix indexed by [int(1..num_sets)] of int(0..n*n*n*n)

such that
   forall i: int(1..num_sets) .
       sums[i] = (sum j: int(1..n) . j*(a[j]=i)) /\
       sums_squared[i] = sum j: int(1..n) . j**2*(a[j]=i)
   ,
   $ same cardinality and sums
   forall i: int(2..num_sets) .
      (sum j: int(1..n) . a[j]=i-1) = (sum j: int(1..n) . a[j]=i) /\
      sums[i-1] = sums[i] /\
      sums_squared[i-1] = sums_squared[i]
   ,
   $ summetry breaking
   a[1] = 1