How to create a list of numbers that make up a certain number

Question

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

Call the addUpList / 2 predicate, it should work as follows:

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

I have so many problems, when I realized this, I start to think that this is impossible. Any ideas? Thanks in advance.

Answer 1

Try the following:

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

Tell me which brands I get. :-)

Answer 2

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

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

To get all of these 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 a post from @hardmath, which gives the same answer with a more detailed explanation.

Answer 3

The example provided in the Question assumes that the compositions (ordered sections) of any positive integer N & leq; 10 are required. Note, however, that the solution [3] for N = 3 was apparently omitted / missed. the number of songs N is 2 ^ (N-1), so N = 10 gives a long list, but not unmanageable.

It is also advisable to collect all such solutions into a list, what findall/3 can do as a whole after we write the predicate composition/2 that generates them.

The idea is to select the first term, something between 1 and N, subtract it from the sum and recursion (stopping with an empty list when the total number reaches zero). SWI-Prolog provides a between/3 predicate that can generate these possible first terms, and Amzi! The prolog provides a similar for/4 predicate. For 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 Prolog source code compiled or interpreted above, a list of all solutions can be made as follows:

 ?- findall(C,composition(3,C),L). C = H126 L = [[1, 1, 1], [1, 2], [2, 1], [3]] 

Of course, for your specific application, some layout of such a list of solutions or the absence of a single list may be required, but this is not clear, since the question is currently formulated.

Answer 4

There are many great answers to this question, but here is another solution to this problem for you. This program differs from others in that it is very efficient and generates unreserved list solutions, which are supposed to be integers that add to the specified number.

 gen(N, L) :- gen(N-1, N, N, FL), dup_n(FL, L). gen(CF, M, M, [CF]). gen(CF, S, M, [CF|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(CF, 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([VF|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). 

What should cause the following behavior:

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

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

Answer 5

This answer is somewhere between the @Kaarel answer and @sharky "effective" answer .

Like the @sharky code, we impose an ordering relationship between adjacent list items to limit the size of the solution space — knowing how to inflate it if we ever need to. Thus, the break_down/2 and gen/2 by @sharky solution sets are equal (excluding list reversal).

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