1

I am trying to perform a sum operation on every result of :

combination(0,_,[]).
combination(K,L,[X|Xs]) :-
   K > 0,
   el(X,L,R),
   K1 is K-1,
   combination(K1,R,Xs).

el(X,[X|L],L).
el(X,[_|L],R) :- el(X,L,R).

For example, the user will enter is_sum_equal_10 ([1,2,3,4,5,6,7]) and the result will be true if the sum of any of the permutations equals 10.

I am struggling with putting it all together, can someone please help me define the is_sum_equal_10 rule that uses the combination rule for each permutation?

1 Answer 1

2

OK, well it's pretty easy to write really, you just need a rule to say if a particular combination sums to 10, and then another extra one to count up through the different sizes of combination lists (which is required due to the way you wrote combination with the K that you need to decrease as you check the rule).

1 ?- [user].
|: combination(0,_,[]).
|: combination(K,L,[X|Xs]) :- K > 0,
|:    el(X,L,R), K1 is K-1, combination(K1,R,Xs).
|: el(X,[X|L],L).
|: el(X,[_|L],R) :- el(X,L,R).
|: 
|: totals_10([],10).
|: totals_10([X|Xs],T) :- N is T+X, totals_10(Xs,N).
|: 
|: is_comb_sum_equal_10(Numbers,_,R) :- combination(R,Numbers,C), totals_10(C,0).
|: is_comb_sum_equal_10(Numbers,N,R) :- Rnext is R+1, Rnext =< N,
|:    is_comb_sum_equal_10(Numbers,N,Rnext).
|: 
|: is_sum_equal_10(Numbers) :- length(Numbers,N), is_comb_sum_equal_10(Numbers,N,0).
|: 
% user://1 compiled 0.13 sec, 1,824 bytes
true.

2 ?- is_sum_equal_10([2,3,5]).
true .

3 ?- is_sum_equal_10([2,235,124,3,3347,5,2373]).
true .

4 ?- is_sum_equal_10([2,235,124,3,3347,6,2373]).
false.

5 ?- is_sum_equal_10([1,1,1,1,1,-1,1,1,1,1,12]).
false.

6 ?- is_sum_equal_10([1,1,1,1,1,-1,1,1,1,1,11]).
true ;
false.

Since you don't care about the actual list or how big it is in the is_sum_equal_10 thing, you can just sum the combinations as you go along, and even better, check the sum is correct as a rule for the base case. I think it's a bit neater if you subtract from the desired total to get to 0 at the base rather than adding up and checking at the end against the value you want. This gives you a very simple single ruleset to look for a certain sum.

7 ?- [user].
|: is_subset_sum(0,[]).
|: is_subset_sum(N,[_|Xs]) :- is_subset_sum(N,Xs).
|: is_subset_sum(N,[X|Xs]) :- R is N-X, is_subset_sum(R,Xs).
|: 
% user://2 compiled 0.03 sec, 540 bytes
true.

8 ?- is_subset_sum(10,[3,5,6]).
false.

9 ?- is_subset_sum(10,[123,4,1,77,3,2,34]).
true .

10 ?- is_subset_sum(11,[0,2,4,6,8,10,12,14,16,18,20,22]).
false.

This approach is of course both much easier to understand, and a lot more efficient.

4
  • Thank you, KernelJ, for such a detailed answer. Just one more thing - in order to simplify the task - I'd like to set the permutation size to a predefined value of 5. So each time, only a permutation set of 5 integers out of a given list will be checked if it sums up to 10. I've tried to set the R value to be 5, but I keep getting a false answer to any calculation attempt. Which value I need to change in order to check a fixed size of permutation set at each attempt, given an unknown lenght of input list? Thank you for your help! Amy
    – Amy
    Dec 13, 2009 at 15:12
  • I think it's pretty obvious how to make a new rule based on the code already there, you just need to use combination and totals_10 in your rule. It's a single line! Have a go at writing it yourself; if you're still having trouble, post what kind of things you tried, and then maybe I can figure out what part you don't understand.
    – KernelJ
    Dec 13, 2009 at 16:04
  • What I've tried was adding an extra line: is_comb_sum_equal_10(Numbers,,5) :- combination(5,Numbers,C), totals_10(C,0). And now I just replaced the initial line with the new line (the one that has 5 instead of R).Working!:) In addition to it, if I want to add another condition, can I write is a new function first_2_last , and then add the condition to the same line, like this: is_comb_sum_equal_10(Numbers,,5) :- combination(5,Numbers,C), totals_10(C,0), first_to_last(C). Will it insure that the new condition will operate on the same current combination of 5 integers out of the whole list?
    – Amy
    Dec 13, 2009 at 16:38
  • Yes, all three conditions must be true at the same time for some set combination C. Prolog checks them from left to right, so the first_to_last condition will only be checked for combinations of 5 things totalling 10.
    – KernelJ
    Dec 13, 2009 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.