如何使用 fd 求解器确定列表中的哪些元素可以求和为给定数字?
How to use an fd solver to determine which elements of a list can sum to a given number?
给定一个可能的加法列表,我想确定哪些(如果有的话)可以形成给定的和。例如,对于 [1,2,3,4,5],我可以将 9 与 [4,5]、[5,3,1] 和 [4,3,2] 相加。
我正在使用 GNU Prolog 并且有类似下面的东西不起作用
numbers([1,2,3,4,5]).
all_unique(_, []).
all_unique(L, [V|T]) :-
fd_exactly(1, L, V),
all_unique(L, T).
fd_sum([], Sum).
fd_sum([H|T], Sum):-
S = Sum + H,
fd_sum(T, S).
sum_clp(N, Summands):-
numbers(Numbers),
length(Numbers, F),
between(1, F, X),
length(S, X),
fd_domain(S, Numbers),
fd_domain(Y, [N]),
all_unique(S, Numbers),
fd_sum(S, Sum),
Sum #= Y,
fd_labeling(S).
我认为主要问题是我没有正确表示对总和的约束?或者可能是其他原因?
我认为将 sublist
的代码混合到 clp 代码中会造成一些混乱。 GNU-Prolog 有一个 sublist/2
谓词,你可以使用它。
您似乎正在使用 fd_sum
构建算术表达式,但它的实现不正确。
sum_exp([], 0).
sum_exp([X|Xs], X+Xse) :-
sum_exp(Xs, Xse).
sum_c(X, N, Xsub) :-
sublist(Xsub, X),
sum_exp(Xsub, Xe),
N #= Xe.
| ?- sum_exp([A, B, C, D], X).
X = A+(B+(C+(D+0)))
yes
| ?- sum_c([1, 2, 3, 4, 5], 9, X).
X = [4,5] ? ;
X = [2,3,4] ? ;
X = [1,3,5] ? ;
(1 ms) no
| ?- length(X, 4), sum_c(X, 4, [A, B]), member(A, [1, 2, 3]).
A = 1
B = 3
X = [_,_,1,3] ? ;
A = 2
B = 2
X = [_,_,2,2] ? ;
A = 3
B = 1
X = [_,_,3,1] ?
yes
以防万一您真的对 CLP(FD) 感兴趣,这里是您更正的程序。
numbers([1,2,3,4,5]).
% note: use builtins where available, both for efficiency and correctness
%all_unique(_, []).
%all_unique(L, [V|T]) :-
% fd_exactly(1, L, V),
% all_unique(L, T).
fd_sum([], 0). % sum_fd_SO.pl:8: warning: singleton variables [Sum] for fd_sum/2
fd_sum([H|T], Sum):-
% note: use CLP(FD) operators and the correct operands
Sum #= S + H,
fd_sum(T, S).
sum_clp(N, S):- % sum_fd_SO.pl:13-23: warning: singleton variables [Summands] for sum_clp/2
numbers(Numbers),
length(Numbers, F),
between(1, F, X),
length(S, X),
fd_domain(S, Numbers),
%fd_domain(Y, [N]),
%all_unique(S, Numbers),
fd_all_different(S),
fd_sum(S, N),
%Sum #= Y,
fd_labeling(S).
测试
?- sum_clp(3,L).
L = [3] ? ;
L = [1,2] ? ;
L = [2,1] ? ;
no
给定一个可能的加法列表,我想确定哪些(如果有的话)可以形成给定的和。例如,对于 [1,2,3,4,5],我可以将 9 与 [4,5]、[5,3,1] 和 [4,3,2] 相加。 我正在使用 GNU Prolog 并且有类似下面的东西不起作用
numbers([1,2,3,4,5]).
all_unique(_, []).
all_unique(L, [V|T]) :-
fd_exactly(1, L, V),
all_unique(L, T).
fd_sum([], Sum).
fd_sum([H|T], Sum):-
S = Sum + H,
fd_sum(T, S).
sum_clp(N, Summands):-
numbers(Numbers),
length(Numbers, F),
between(1, F, X),
length(S, X),
fd_domain(S, Numbers),
fd_domain(Y, [N]),
all_unique(S, Numbers),
fd_sum(S, Sum),
Sum #= Y,
fd_labeling(S).
我认为主要问题是我没有正确表示对总和的约束?或者可能是其他原因?
我认为将 sublist
的代码混合到 clp 代码中会造成一些混乱。 GNU-Prolog 有一个 sublist/2
谓词,你可以使用它。
您似乎正在使用 fd_sum
构建算术表达式,但它的实现不正确。
sum_exp([], 0).
sum_exp([X|Xs], X+Xse) :-
sum_exp(Xs, Xse).
sum_c(X, N, Xsub) :-
sublist(Xsub, X),
sum_exp(Xsub, Xe),
N #= Xe.
| ?- sum_exp([A, B, C, D], X).
X = A+(B+(C+(D+0)))
yes
| ?- sum_c([1, 2, 3, 4, 5], 9, X).
X = [4,5] ? ;
X = [2,3,4] ? ;
X = [1,3,5] ? ;
(1 ms) no
| ?- length(X, 4), sum_c(X, 4, [A, B]), member(A, [1, 2, 3]).
A = 1
B = 3
X = [_,_,1,3] ? ;
A = 2
B = 2
X = [_,_,2,2] ? ;
A = 3
B = 1
X = [_,_,3,1] ?
yes
以防万一您真的对 CLP(FD) 感兴趣,这里是您更正的程序。
numbers([1,2,3,4,5]).
% note: use builtins where available, both for efficiency and correctness
%all_unique(_, []).
%all_unique(L, [V|T]) :-
% fd_exactly(1, L, V),
% all_unique(L, T).
fd_sum([], 0). % sum_fd_SO.pl:8: warning: singleton variables [Sum] for fd_sum/2
fd_sum([H|T], Sum):-
% note: use CLP(FD) operators and the correct operands
Sum #= S + H,
fd_sum(T, S).
sum_clp(N, S):- % sum_fd_SO.pl:13-23: warning: singleton variables [Summands] for sum_clp/2
numbers(Numbers),
length(Numbers, F),
between(1, F, X),
length(S, X),
fd_domain(S, Numbers),
%fd_domain(Y, [N]),
%all_unique(S, Numbers),
fd_all_different(S),
fd_sum(S, N),
%Sum #= Y,
fd_labeling(S).
测试
?- sum_clp(3,L).
L = [3] ? ;
L = [1,2] ? ;
L = [2,1] ? ;
no