My task is: Find the number of partitions of a positive integer in the amount of natural terms. For example: N=5. Answer is 7, because 5: {1,1,1,1,1}, {2,1,1,1}, {2,2,1}, {3,1,1}, {3,2}, {4,1}, {5}
I wrote a solution on JS:
function pcount(number, limit) {
if (limit === 0) {
if (number === 0) {
return 1;
}
return 0;
}
if (limit <= number) {
return pcount(number, limit - 1) + pcount(number - limit, limit);
}
return pcount(number, number);
}
but now i'm trying to write it using Prolog, but there are some difficulties with pcount(number, limit - 1) + pcount(number - limit, limit);
statement.
Here is my code:
PREDICATES
check(integer,integer,integer)
check(integer,integer)
CLAUSES
check(0,0,Result):-
Result=1.
check(_,0,Result):-
Result=0.
check(Number,Limit,Result):-
Limit<=Number,!,
NN=Limit-1,
RR=Number-Limit,
check(Number,NN,Result1),
check(RR,Limit,Result2),
Result=Result1+Result2.
check(A,B):-
check(A,B,X),
write(X).
%check(number, limit - 1) + check(number - limit, limit);
GOAL
check(2,2).
but it doesn't work. Error at this predicate: check(Number,Limit,Result)
. How can I combine the results of two calls of predicates: check(Number, Limit-1)+check(Number-Limit,Limit)
?
What you have is very close to correct, but requires a little more constraint. The existing clause is recursing into negative values of Limit
. Here's a minor update which should resolve that issue, along with some minor tweaks:
check(0, 0, 1).
check(N, 0, 0) :-
N > 0. % Added constraint N > 0
% avoids overlap with first clause
check(Number, Limit, Result):-
Limit > 0, % Added constraint Limit > 0 avoids overlap
% with first clause and negative values
Limit <= Number, !,
NN = Limit - 1,
RR = Number - Limit,
check(Number, NN, Result1),
check(RR, Limit, Result2),
Result = Result1 + Result2.
check(Number, Limit, Result) :- % Case were Limit > Number as in your
Limit > Number, % original non-Prolog code
check(Number, Number, Result).
check(A, B):-
check(A, B, X),
write(X).