How to create a list of numbers that add up to a s

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

There are plenty of great answers to this question already, but here is another solution to this problem for you to consider. This program differs from the others in that it is very efficient, and generates non-redundant solutions of lists which are assumed to represent sets of integers which add up to the specified number.

gen(N, L) :-
    gen(N-1, N, N, FL),
    dup_n(FL, L).
gen(C-F, M, M, [C-F]).
gen(C-F, S, M, [C-F|R]) :-
    S < M, C > 1,
    C0 is C - 1,
    F0 is floor(M / C0),
    S0 is S + (C0 * F0),
    gen(C0-F0, S0, M, R).
gen(C-F, S, M, R) :-
    F > 0,
    F0 is F - 1,
    S0 is S - C,
    gen(C-F0, S0, M, R).

dup_n([], []).
dup_n([_-0|R], L) :-
    !, dup_n(R, L).
dup_n([V-F|R], [V|L]) :-
    F0 is F - 1,
    dup_n([V-F0|R], L).

Your implementation of addUpList/2 can be achieved by:

addUpList(N, P) :-
    findall(L, gen(N, L), P).

Which should give you the following behaviour:

?- addUpList(4,L).
L = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]].

Note that the list containing one 2 and two 1s only appears once in this result set; this is because gen/4 computes unique sets of integers which add up to the specified number.

Answer 2

This answer is somewhere between @Kaarel's answer and @sharky's "efficient" answer.

Like @sharky's code, we impose an ordering relation between adjacent list items to restrict the size of the solution space---knowing how to inflate it if we ever need to. So the solution sets of break_down/2 and gen/2 by @sharky are equal (disregarding list reversal).

And as for performance, consider:

?- time((break_down(40,_),false)).
% 861,232 inferences, 0.066 CPU in 0.066 seconds (100% CPU, 13127147 Lips)
false.

?- time((gen(40,_),false)).
% 8,580,839 inferences, 0.842 CPU in 0.842 seconds (100% CPU, 10185807 Lips)
false.

Answer 3

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 4

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.

Answer 5

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.