7

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.

repeat
  • 18,496
  • 4
  • 54
  • 166
Nick
  • 71
  • 1
  • 2
  • 1
    Not impossible, but you won't want to run this thing for very large integers! Some insight may be gained from reading http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum. – Ray Toal Jul 26 '11 at 04:40
  • Mmmmm I see... but those answers depend on passing them a set of numbers as input. In my case, I need to generate the set of numbers... i don't know if I'm making myself clear. – Nick Jul 26 '11 at 04:54
  • No, you are quite clear; the other question addresses the subset sum problem for given addends, while you want all combinations. It is similar but not the same. Your problem will generate insanely huge lists. Just out of curiosity is this homework? What do you want to do with the elements of the resulting list. Do you have any idea how large the result list is for a given sum? – Ray Toal Jul 26 '11 at 05:09
  • 1
    I am aware it can generate huge lists, but I only need addends that add up between [1 ... 10] (making the largest possible list [1,1,1,1,1,1,1,1,1,1]). The entire list will be passed on to another predicate in order to build an R-ary tree. And frankly, yes, it is homework, i`ve been stuck trying to figure it out for a week at least. – Nick Jul 26 '11 at 05:32
  • Just want to comment that this is related to the enumeration of all possible integer partitions, there are a few known methods for doing that. Inclusion of relevant tags would be helpful. – prusswan Jul 26 '11 at 20:40

5 Answers5

4

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. :-)

Enigmativity
  • 113,464
  • 11
  • 89
  • 172
  • Good God! That`s it! I think that's just what I need, I`m gonna have to look at it close. Thank you very much! – Nick Jul 26 '11 at 05:53
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.

Kaarel
  • 10,554
  • 4
  • 56
  • 78
1

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.
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
1

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.

hardmath
  • 8,753
  • 2
  • 37
  • 65
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.