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