$ $ 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: $ $""" $ $ 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