Получить все подмножества, которые суммируют до значения N в прологе

Question

Это постановка проблемы:

Учитывая список целых чисел 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и предупреждение о LR переменная в предложении проверки, переменная не связана. Я не уверен, что я делаю неправильно или есть более простое решение для этого. Любая помощь приветствуется.

Answer 1

Я думаю, что ваша последняя процедура должна прочитать

%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]])

Answer 2

В этом ответе мы используем clpfd:

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