30
31:- module(count,
32 [ proof_count/2, 33 proof_count/3, 34 answer_count/3, 35 answer_count/4, 36 answer_set/3, 37 answer_set/4, 38 answer_pair_set/5, 39 unique_solution/2 40 ]). 41:- use_module(library(nb_set)). 42:- use_module(library(rbtrees)). 43:- use_module(library(nb_rbtrees)).
62:- meta_predicate
63 proof_count(0, -),
64 proof_count(0, +, -),
65 answer_count(?, 0, -),
66 answer_count(?, 0, +, -),
67 answer_set(?, 0, -),
68 answer_set(?, 0, +, -),
69 answer_pair_set(?, 0, +, +, -),
70 unique_solution(0, -).
82proof_count(Goal, Count) :-
83 proof_count(Goal, infinite, Count).
84
85proof_count(Goal, Max, Count) :-
86 State = count(0),
87 ( Goal,
88 arg(1, State, N0),
89 N is N0 + 1,
90 nb_setarg(1, State, N),
91 N == Max
92 -> Count = Max
93 ; arg(1, State, Count)
94 ).
102answer_count(T, G, Count) :-
103 answer_count(T, G, infinite, Count).
104
105answer_count(T, G, Max, Count) :-
106 empty_nb_set(Set),
107 C = c(0),
108 ( G,
109 add_nb_set(T, Set, true),
110 arg(1, C, C0),
111 C1 is C0+1,
112 nb_setarg(1, C, C1),
113 C1 == Max
114 -> Count = Max
115 ; arg(1, C, Count)
116 ).
128answer_set(T, G, Ts) :-
129 findall(T, G, Raw),
130 sort(Raw, Ts).
131
132answer_set(T, G, Max, Ts) :-
133 empty_nb_set(Set),
134 State = count(0),
135 ( G,
136 add_nb_set(T, Set, true),
137 arg(1, State, C0),
138 C is C0 + 1,
139 nb_setarg(1, State, C),
140 C == Max
141 -> true
142 ; true
143 ),
144 nb_set_to_list(Set, Ts).
152answer_pair_set(P, G, MaxKeys, MaxPerKey, Groups) :-
153 P = K-V,
154 ( MaxPerKey = inf
155 -> true
156 ; TooMany is MaxPerKey+1,
157 dif(New, values(TooMany))
158 ),
159 rb_empty(Tree),
160 State = keys(0),
161 ( G,
162 add_pair(Tree, K, V, New),
163 New == new_key,
164 arg(1, State, C0),
165 C is C0+1,
166 nb_setarg(1, State, C),
167 C == MaxKeys
168 -> true
169 ; true
170 ),
171 groups(Tree, Groups).
172
173add_pair(T, K, V, New) :-
174 nb_rb_get_node(T, K, N), !,
175 nb_rb_node_value(N, NV),
176 NV = k(Count, VT),
177 ( nb_rb_get_node(VT, V, _)
178 -> New = false
179 ; NewCount is Count + 1,
180 New = values(NewCount),
181 nb_rb_insert(VT, V, true),
182 nb_setarg(1, NV, NewCount)
183 ).
184add_pair(T, K, V, new_key) :-
185 rb_one(V, true, RB),
186 nb_rb_insert(T, K, k(1, RB)).
187
188rb_one(K, V, Tree) :-
189 rb_empty(T0),
190 rb_insert(T0, K, V, Tree).
191
192groups(Tree, Groups) :-
193 rb_visit(Tree, Pairs),
194 maplist(expand_values, Pairs, Groups).
195
196expand_values(K-k(_Count,T), K-Vs) :-
197 rb_keys(T, Vs).
210unique_solution(Goal, Solution) :-
211 State = state(false, _),
212 ( Goal,
213 ( arg(1, State, false)
214 -> nb_setarg(1, State, true),
215 nb_setarg(2, State, Solution),
216 fail
217 ; arg(2, State, Answer),
218 Answer =@= Solution
219 -> fail
220 ; !, fail 221 )
222 ; arg(1, State, true),
223 arg(2, State, Solution)
224 )
This module provides various ways to count solutions
This module is based on a similar collection introduces in the first ClioPatria release. Most names have been changed to describe the semantics more accurately.
The predicates in this library provide space-efficient solutions, avoiding findall/setof. Most predicates come with a variant that allows limiting the number of answers.