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 | %-----------------------------------------------------------------------------% % Partitioning problem % % Guido Tack % 05/2009 % % % Partition 2*n numbers into two groups, each of size n, such that % their sums are equal and the sums of their squares are equal. % include "globals.mzn" ; %-----------------------------------------------------------------------------% % Instance %-----------------------------------------------------------------------------% n = 32; %-----------------------------------------------------------------------------% % Model %-----------------------------------------------------------------------------% int : n; array [1..n] of var 1..2*n: x; array [1..n] of var 1..2*n: y; constraint true % Break symmetries by ordering numbers in each group /\ forall (i in 2..n) (x[i-1] < x[i] /\ y[i-1] < y[i]) % Break symmetries by ordering the groups /\ x[1] < y[1] % Partition the numbers /\ (alldifferent(x++y)) :: bounds % The sums are equal /\ sum (x) = 2*n*(2*n+1) div 4 /\ sum (y) = 2*n*(2*n+1) div 4 % The sums of the squares are equal /\ let { array [1..n] of var 1..4*n*n: sx, array [1..n] of var 1..4*n*n: sy } in forall (i in 1..n) (sx[i]=x[i]*x[i] /\ sy[i] = y[i]*y[i]) /\ sum (sx) = 2*n*(2*n+1)*(4*n+1) div 12 /\ sum (sy) = 2*n*(2*n+1)*(4*n+1) div 12 ; solve ::int_search(x++y,first_fail,indomain_min,complete) satisfy ; output [ "x = " , show (x), "\n" , "y = " , show (y), "\n" , "sum = " , show (2*n*(2*n+1) div 4), "\n" , "sum of squares = " , show (2*n*(2*n+1)*(4*n+1) div 12), "\n" ]; |