049: Number Partitioning

/*

  Set partition problem in ECLiPSe.

  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:
   <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
  * Comet   : http://www.hakank.org/comet/set_partition.co


  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).