Partitioning a large integer using Prolog

Question

I've been trying to teach myself Prolog for a few weeks. Right now I'm trying to find all ways to make a large integer from several smaller integers, using a predicate partition/3 that I want to work like:

| ?- partition(4, [1, 2, 3], X).

X = [1, 1, 1, 1] ? ;
X = [1, 1, 2] ? ;
X = [1, 3] ? ;
X = [2, 2] ? ;
no

thus finding all ways to make 4 from 1, 2 and 3. Duplicate solutions like [1, 2, 1] and [2, 1, 1] are fine but probably not hard to avoid. Here's what I have right now:

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).
% if the first input IH can be subtracted from N,
% do so into M and push IH into the output list [OH|OT]

partition(N, [_|IT], Output) :-
  N =< 0, fail;
  partition(N, IT, Output). 
% after trying the first input term, try the others

The idea is that N will eventually become zero, and the subtractions that got it there will be placed in the third argument as a list. The third and fourth rules only operate on positive integers, the second rule says not to run out of inputs, and the first rule signals that the partition is valid when N reaches zero. Problem is, I only get:

| ?- partition(4, [1, 2, 3], X).

no

The first and second rules make sense to me, the third and fourth seem iffy but I can't find anything specifically wrong with them. I thought that the output tail OT might not get instantiated when M becomes zero, but the first rule takes care of that. Or is there some fundamental misunderstanding of how Prolog works (which seems likely to happen often for me)?

Also, are the N =< 0, fail; parts redundant? They seem redundant but I can't be sure until I get something that works.

Edit: I'm using GNU Prolog.

Answer 1

You have one issue here, with the comparison of N to IH:

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

It should be N >= IH.

Consider your example partition(4, [1, 2, 3], X):

1. It matches predicate 3, which in turn checks partition(3,[1,2,3],OT)
2. partition(3,[1,2,3],OT) matches the third predicate, that checks partition(2,[1,2,3],OT).
3. partition(2,[1,2,3],OT) matches the third predicate, that checks partition(1,[1,2,3],OT).
4. partition(1,[1,2,3],OT) matches the fourth predicate, since 1 > 1 fails. Checks partition(1,[2,3],OT).
5. partition(1,[2,3],OT) will match the fourth predicate to the end, and fail when the list is empty.