1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | $ $ Set partition problem in Essence' $ $ $ Problem formulation from $ """ $ This is a partition problem. $ Given the set S = {1, 2, ..., n}, $ it consists in finding two sets A and B such that: $ <ul> $ <li>A U B = S,</li> $ <li>|A| = |B|,</li> $ <li>sum(A) = sum(B),</li> $ <li>sum_squares(A) = sum_squares(B).</li> $ </ul> $""" $ $ 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 |