How to create a list of numbers that add up to a specific number

Question

I need some help writing a predicate in Prolog that, given a number as input, returns a list of lists with numbers that add up to it.

Let's call the predicate addUpList/2, it should work like this:

?- addUpList(3,P).
P = [[1,2], [2,1], [1,1,1]].       % expected result

I'm having so much trouble figuring this out I'm beginning to think it's impossible. Any ideas? Thanks in advance.

Answer 1

Try this:

condense([], Rs, Rs).
condense([X|Xs], Ys, Zs) :-
    condense(Xs, [X|Ys], Zs).
condense([X, Y|Xs], Ys, Zs) :-
    Z is X + Y,
    condense([Z|Xs], Ys, Zs).

condense(Xs, Rs) :-
    condense(Xs, [], Rs).

expand(0, []).
expand(N, [1|Ns]) :-
    N > 0,
    N1 is N - 1,
    expand(N1, Ns).

addUpList(N, Zs) :-
    expand(N, Xs),
    findall(Ys, condense(Xs, Ys), Zs).

Let me know what marks I get. :-)

Answer 2

The rule num_split/2 generates ways of splitting a number into a list, where the first element X is any number between 1 and N and the rest of the list is a split of N-X.

num_split(0, []).
num_split(N, [X | List]) :-
    between(1, N, X),
    plus(X, Y, N),
    num_split(Y, List).

In order to get all such splits, just call findall/3 on num_split/2.

add_up_list(N, Splits) :-
    findall(Split, num_split(N, Split), Splits).

Usage example:

?- add_up_list(4, Splits).
Splits =
   [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]].

See also the post by @hardmath which gives the same answer with a bit more explanation.

Answer 3

The example given in the Question suggests that compositions (ordered partitions) of any positive integer N ≤ 10 are wanted. Note however that the solution [3] for N=3 seems to have been omitted/overlooked. The number of compositions of N is 2^(N-1), so N=10 gives a long list but not an unmanageable one.

It is also desired to collect all such solutions into a list, something that findall/3 can do generically after we write a predicate composition/2 that generates them.

The idea is to pick the first summand, anything between 1 and N, subtract it from the total and recurse (stopping with an empty list when the total reaches zero). SWI-Prolog provides a predicate between/3 that can generate those possible first summands, and Amzi! Prolog provides a similar predicate for/4. For the sake of portability we write our own version here.

summand(Low,High,_) :-
    Low > High,
    !,
    fail.
summand(Low,High,Low).
summand(Low,High,Val) :-
    Now is Low + 1,
    summand(Now,High,Val).

composition(0,[ ]).
composition(N,[H|T]) :-
    summand(1,N,H),
    M is N - H,
    composition(M,T).

Given the above Prolog source code, compiled or interpreted, a list of all solutions can be had in this way:

?- findall(C,composition(3,C),L).

C = H126
L = [[1, 1, 1], [1, 2], [2, 1], [3]] 

Of course some arrangement of such a list of solutions or the omission of the singleton list might be required for your specific application, but this isn't clear as the Question is currently worded.