如何使用 fd 求解器确定列表中的哪些元素可以求和为给定数字？

Question

给定一个可能的加法列表，我想确定哪些（如果有的话）可以形成给定的和。例如，对于 [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).

我认为主要问题是我没有正确表示对总和的约束？或者可能是其他原因？

Answer 1

我认为将 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

Answer 2

以防万一您真的对 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

如何使用 fd 求解器确定列表中的哪些元素可以求和为给定数字？

How to use an fd solver to determine which elements of a list can sum to a given number?

prolog

clpfd

gnu-prolog