Recursive Prolog predicate?

Question

I am currently working on a project and I want to implement a helper predicate in Prolog

break_down(N, L)

which works as follows

 ?- break_down(1,L). L = [1] ; false. ?- break_down(4,L). L = [1, 1, 1, 1] ; L = [1, 1, 2] ; L = [1, 3] ; L = [2, 2] ; L = [4] ; false. 

etc. for any natural N.

I tried and implemented a code that only generates the first result, and I cannot get the rest of the results, and this is my code

 break_down(1,[1]). break_down(N,L):- N>0, N1 is N-1, break_down(N1,L1), append(L1,[1],L). 

which generates only the first output result:

  L = [1, 1, 1, 1] ; 

any suggestion how to edit my code to get the rest?

Answer 1

Here's a direct recursive implementation using simple integer arithmetic and backtracking:

 break_down(N,L) :- break_ref_down(N,1,L). % reference item is initially 1 break_ref_down(0,_,[]). break_ref_down(N,Z0,[Z|Zs]) :- between(Z0,N,Z), % multiple choices N0 is NZ, break_ref_down(N0,Z,Zs). % pass on current item as reference 

Request example:

 ?- break_down(8,Zs). Zs = [1,1,1,1,1,1,1,1] ; Zs = [1,1,1,1,1,1,2] ; Zs = [1,1,1,1,1,3] ; Zs = [1,1,1,1,2,2] ; Zs = [1,1,1,1,4] ; Zs = [1,1,1,2,3] ; Zs = [1,1,1,5] ; Zs = [1,1,2,2,2] ; Zs = [1,1,2,4] ; Zs = [1,1,3,3] ; Zs = [1,1,6] ; Zs = [1,2,2,3] ; Zs = [1,2,5] ; Zs = [1,3,4] ; Zs = [1,7] ; Zs = [2,2,2,2] ; Zs = [2,2,4] ; Zs = [2,3,3] ; Zs = [2,6] ; Zs = [3,5] ; Zs = [4,4] ; Zs = [8] ; false. 

Answer 2

Here's an implementation based on clpfd .

 :- use_module(library(clpfd)). 

Since the break_downFD/2 predicate is not recursive, the code is readable and simple:

 break_downFD(N,Zs) :- length(Max,N), % multiple choices append(_,Zs,Max), Zs ins 1..N, sum(Zs,#=,N), chain(Zs,#=<), % enforce sequence is non-descending labeling([],Zs). % multiple choices, possibly 

Example request using SWI-Prolog:

 ?- break_downFD(6,Zs). Zs = [1,1,1,1,1,1] ; Zs = [1,1,1,1,2] ; Zs = [1,1,1,3] ; Zs = [1,1,2,2] ; Zs = [1,1,4] ; Zs = [1,2,3] ; Zs = [2,2,2] ; Zs = [1,5] ; Zs = [2,4] ; Zs = [3,3] ; Zs = [6] ; false.