2

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)?

HelterShelter
  • 171
  • 2
  • 11
  • Prolog doesn't have *functions* but *predicates*. A predicate succeeds or fails and does not return a value. But you can instantiate an variable argument with a result (*e.g.*, `pcount(5, 5, Result)`). I'm not sure why you're concerned about that. It's a fundamentally different language. As far as just mapping an if-then-else, [this question](http://stackoverflow.com/questions/29051798/whats-the-meaning-of-prolog-operator) might be of interest to you. – lurker Mar 14 '15 at 19:22
  • I keep forgetting that Turbo/Visual prolog allows `<=` in place of `=<`. :p – lurker Mar 14 '15 at 19:26
  • You might want to go through a basic Prolog tutorial before tackling this problem. Expressions such as, `pcount(Number,Limit-1)+pcount(Number-Limit,Limit)` arent going to do at all what you think it's going to do. – lurker Mar 14 '15 at 19:32
  • ty, but `Goal1 -> Goal2 ; Goal3` statement doesn't work in visual prolog. – HelterShelter Mar 14 '15 at 21:20
  • Unfortunately, Visual Prolog deviates significantly from what is considered to be standard Prolog. What you've updated, though, is very close to correct. Your second clause, `check(_, 0, Result)` needs to ensure that the number is > 0 to avoid overlap with the first case. And you need a clause to handle `Number > Limit`. What exactly is the *error at this predicate...*? FYI, you can just write, `check(0, 0, 1).` instead of `check(0, 0, R) :- R = 1.` (I *think* Visual Prolog lets you do that - it's standard Prolog.) – lurker Mar 14 '15 at 21:58
  • Minor correction to my comment: you don't need a clause for `Number > Limit` if that's not a successful case (you want that case to fail). It's a success case in your original javascript-ish code. – lurker Mar 14 '15 at 23:01
  • I have error: `Message:1010 Stack overflow`. And yes, I rewrote my predicates to `check(0,0,1)` and `check(A,0,0):- A>0`. It works, ty – HelterShelter Mar 15 '15 at 09:47
  • But I can't understand what wrong in my recursion and where in stack overflow. – HelterShelter Mar 15 '15 at 09:58

1 Answers1

1

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).
lurker
  • 56,987
  • 9
  • 69
  • 103