049: Number Partitioning

/*

  Set partition problem in B-Prolog.

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

  This model just implementa a two set version.

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my B-Prolog page: http://www.hakank.org/bprolog/

*/

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

% find all (7) solutions for N = 16.
go :-
        findall(Sets,set_partition(16, Sets),L), 
        length(L,Len),
        format("It was ~d solutions.\n", [Len]).


go2 :-
        N :: 2..50,
        indomain(N),
        once(set_partition(N, _Sets)), 
        nl,fail.



set_partition(N,Sets) :-

        writeln('\nN':N),

        (N mod 2 > 0 -> format("~d is not a multiple of 2.\n", [N]), fail ; true ),
        (N mod 4 > 0 -> format("~d is not a multiple of 4.\n", [N]), fail ; true ),

        N2 is N //2,

        [A,B] :: {}..{1..N},
        Sets = [A,B],

        % same cardinality
        #A #= N2,
        #A #= #B,

        % A and B are disjoint
        A #<> B,

        % Symmetry breaking: 1 is in the A set
        1 #<- A,

        % All numbers 1..N must be in some set
        foreach(I in 1..N, (I #<- A ; I #<- B)),

        % It seems that we must have the labeling
        % already here...
        indomain(A),
        indomain(B),

        set_to_list(A,AList),
        set_to_list(B,BList),


        % sum of the sets must be equal
        ASum #= sum(AList),
        BSum #= sum(BList),
        ASum #= BSum,

        % sum of the squares must be equal
        ASumSquared #= sum([ T**2 : I in 1..AList^length, [T], T @= AList[I]]),
        BSumSquared #= sum([ T**2 : I in 1..BList^length, [T], T @= BList[I]]),

        ASumSquared #= BSumSquared,

        % labeling([ASum,BSum,ASumSquared,BSumSquared]),

        writeln(A),
        writeln(B),
        writeln(sums:[ASum,BSum]),
        writeln(sumSquares:[ASumSquared,BSumSquared]),
        nl.