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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | /* Set partition problem in ECLiPSe. 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> """ Compare with the following models: * MiniZinc: http://www.hakank.org/minizinc/set_partition.mzn * Gecode/R: http://www.hakank.org/gecode_r/set_partition.rb Model created by Hakan Kjellerstrand, hakank@gmail.com See also my ECLiPSe page: http://www.hakank.org/eclipse/ Model simplified by Joachim Schimpf */ % Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ :-lib(ic). :-lib(ic_sets). % find all (7) solutions for N = 16. go :- N = 16, NumSets = 2, set_partition( N , NumSets , Sets , Sums ), writeln(sets: Sets ), writeln(sums: Sums ), nl, fail. % % check for a solution between N = 17 and 32 % go2 :- ic : '::' ( N ,17..32), indomain( N ), NumSets = 2, writeln(n: N ), set_partition( N , NumSets , Sets , Sums ), writeln(sets: Sets ), writeln(sums: Sums ), nl. % % Here we find the minimal N and NumSets for % a solution to the problem. % go3 :- N #:: 2..20, NumSets #:: 3..9, indomain( N ), indomain( NumSets ), writeln([n: N ,num_sets: NumSets ]), set_partition( N , NumSets ). set_partition( N , NumSets , Sets , [ Sum , SumSquared ]) :- % create list of sets intsets( Sets , NumSets ,1, N ), % create the universe for partition_set % and the weights for weight/3 below. dim( Weights ,[ N ]), dim( Weights2 ,[ N ]), ( for ( I ,1, N ), foreach ( I , Universe ), foreacharg ( I , Weights ), foreacharg ( W2 , Weights2 ) do W2 is I * I ), % Sets must be a partition of the Universe partition_set( Sets , Universe ), % all sets must have the same cardinality _C ( foreach ( Set , Sets ), param ( _C ) do #( Set , _C ) ), % all sums and all squared sums must be equal ( foreach ( Set , Sets ), param ( Weights , Weights2 , Sum , SumSquared ) do weight( Set , Weights , Sum ), weight( Set , Weights2 , SumSquared ) ), % symmetry breaking [ FirstSet | _ ] = Sets , 1 in FirstSet , % % search % label_sets( Sets ). % % labeling the sets % label_sets([]). label_sets([ S | Ss ]) :- insetdomain( S ,increasing,big_first,in_notin), label_sets( Ss ). % % Partitions the list of sets S into disjoint sets. % All elements in the universe Universe must be % included in exactly one of the sets. % partition_set( S , Universe ) :- all_disjoint( S ), all_union( S , Universe ). |