Получить все подмножества, что сумма до значения 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, проще и быстрее
• у вас есть предел 2/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.