3

这是问题陈述：

给定一个整数列表 L 和一个整数 S，生成所有元素加起来为 S 的子列表。

这是我的解决方案：

domains
        list=integer*
        clist=list*
predicates
        sum(list,integer)
        check(clist,clist,integer)
        gensub(list,list)
        getsub(list,clist,integer)
clauses
        %gets all possible subsets with gensub and findall, binds them to
        %and then checks the subsets to see if the elements add up to S
        %and adds the correct ones to Rez.
        %Goal example: getsub([1,2,5,6],X,7)
        getsub([], [], _).
        getsub(L, Rez, S):-
                findall(LR, gensub(L,LR), X),
                check(X, Rez, S).

        %generates all possible subsets of the given set
        gensub([], []).
        gensub([E|Tail], [E|NTail]):-
                gensub(Tail, NTail).
        gensub([_|Tail], NTail):-
                gensub(Tail, NTail).

        %checks if the sum of the elements of a list is S
        sum([], S):-S=0.
        sum([H|T], S):-
                N=S-H,
                sum(T, N).

        %checks if each sublist of a given list of lists, has the sum of elements S
        check([], [], S).
        %the LR variable here gives a warning after entering the goal
        check([H|T], [H|LR], S):-
                sum(H, S).

因此，在我运行它并被要求输入目标之后，我尝试这样做getsub([1,2,5,6],X,7) 以获取其元素加起来为 7 的所有子集，但我得到一个No Solution, 和 check 子句中变量的警告LR，变量是不受约束。我不确定我做错了什么，或者是否有更简单的解决方案。任何帮助表示赞赏。

4

2 回答 2

3

我认为你的最后一个程序应该是

%checks if each sublist of a given list of lists, has the sum of elements S
check([], [], _).
%the LR variable here gives a warning after entering the goal
check([H|T], [H|LR], S):-
    sum(H, S),
    !, check(T, LR, S).
check([_|T], LR, S):-
    check(T, LR, S).

然后，一些注意事项：

  • 为什么要生成所有子集，然后过滤掉？在 findall 中“推送”测试，它更容易更快
  • 你有一个 sum/2 谓词，如果它按照它所说的去做，它可能会更有用。就这个：

--

% sum elements of a list
sum([], 0).
sum([H|T], S):-
    sum(T, N),
    S is N+H.

（说实话，我用这个测试过，得到[[1,6],[2,5]]）

于 2013-11-20T10:19:52.353 回答
2

在这个答案中，我们使用：

:- use_module(library(clpfd)).

要获取所有可能的子列表，我们使用sublist_of/2：

sublist_of(Sub,List) :-
   list_sub(List,Sub).

sublist_of/2基于辅助谓词list_sub/2：

list_sub([]    ,[]).
list_sub([_|Xs],Ys) :-
   list_sub(Xs,Ys).
list_sub([X|Xs],[X|Ys]) :-
   list_sub(Xs,Ys).

让我们把它放在一起！

list_sublist_sum(Xs,Zs,Sum) :-
   sublist_of(Zs,Xs),
   sum(Zs,#=,Sum).

示例查询：

?- list_sublist_sum([3,34,4,12,5,2],Zs,9).
  Zs = [4,5]
; Zs = [3,4,2]
; false.
于 2015-08-04T06:37:36.180 回答