Distinct Prime Partitions in Prolog

Question

I need to enumerate all the ways of partitioning a given number n into a sum of one or more distinct primes, a + b + ... + m in Prolog

For example:

Given an integer n, the program should write the appropriate sums to standard output. If n = 20, for example, the program might print

2 + 5 + 13
2 + 7 + 11
3 + 17
7 + 13

n can be any number, and there is no restriction on run-time.

Here is what I have:

partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.

partition(N, [IH|IT], [OH|OT]) :-
    N =< 0, fail;
    N >= IH, M is N-IH, OH = IH,
    partition(M, [IH|IT], OT).

partition(N, [_|IT], Output) :-
    N =< 0, fail;
    partition(N, IT, Output).

partition(N, Output) :-
    generatePrime(N,L),
    partition(N, L, Output).

generatePrime(1, []) :- !.
generatePrime(N, X) :-
    not(isPrime(N)), !,
    Z is N-1,
    generatePrime(Z,X).
generatePrime(N, [N | X]) :-
    Z is N-1,
    generatePrime(Z,X).

isPrime(2).
isPrime(P) :-
    P > 2,
    isDivisible(P, P-1). 

isDivisible(P,X) :-
    X > 1,
    P mod X =\= 0,
    isDivisible(P, X-1).
isDivisible(_, X) :-
    1 is X.

Currently, I try running something like this:

[?- partition(5, X).

and I get duplicate prompts of [5] and [3,2]. There is also another type of problem when I use bigger numbers like n = 20, as I get prompts with duplicate primes like [2,2,2,2,2,2,2,2,2,2].

I am very new to prolog, and I am sure there might even be an easier way of doing this problem, but I'm not sure where I am tripping up in the code.

Answer 1

Your not so far...

The bigger problem is the way your'r calling partition/3

partition(5, generatePrime(5,Y), X)

partition/3 expect a list for the second term, not generatePrime(5, Y).

I suggest you to add a partition/2 made as follows

partition(N, Output) :-
    generatePrime(N, L),
    partition(N, L, Output).

and call this version of partition

partition(5, X)

There is something else wrong because this call return more time the same response (return, in X, [5] four times and [3,2] two times).

I'll give a look at it to see if I see the problem

--- EDIT ---

Sorry but I have big problems understandign Prolog code with cuts (!), fail and or (;).

It's a problem of mine, I suppose.

I've modified your partition/3 in the following way

partition(0, _, []).

partition(N, [H | It], [H | Ot]) :-
   N >= H,
   M is N-H,
   partition(M, [H | It], Ot).

partition(N, [_ | It], O) :-
   N > 0, 
   partition(N, It, O).

This should avoid repetitions of lists

If you want avoid duplicate primes in the same list (if you don't accept [3, 3, 2] or [2, 2, 2, 2] for 8 because a prime repeated), you should avoid to reuse H (IH in your original code) in the following call to partition/3.

I mean that the following clause

partition(N, [H | It], [H | Ot]) :-
   N >= H,
   M is N-H,
   partition(M, [H | It], Ot).

should become

partition(N, [H | It], [H | Ot]) :-
   N >= H,
   M is N-H,
   partition(M, It, Ot).