List of factorials in Prolog

Question

I'm having trouble solving the following exercise...

A factorial can be described in Prolog as:

factorial(0, 1).
factorial(N, F) :-
   N1 is N - 1,
   factorial(N1, F1),
   F is N * F1.

I need to expand this code in order to return a list of all previous factorials until N. But it returns only the first factorial (1), and then the error: ERROR: Out of local stack. Here is my code:

insertList(H, L, [H|L]) :-
   !.

factorial(0, 1, [1]).
factorial(N, F, L) :-
   N1 is N - 1,
   factorial(N1, F1, L),
   F is N * F1,
   insertList(F, L, [F|L]). 

list_factorial(X, L) :-
   factorial(X, F, L).

What am I doing wrong?

`factorial(0,0)` loops. Add at least `N > 0` to the rule! – false Apr 13 '15 at 20:49 — false, Apr 13 '15 at 20:49

repeat · Answer 1 · 2015-12-06T22:10:48.840

Here's an implementation in pure prolog with clpfd:

:- use_module(library(clpfd)).

list_factorial([1], 0).
list_factorial(Zs0, N) :-
   length(Zs0, N),
   N #> 0,
   list_n_fac(Zs0, 1, 1).

list_n_fac([], _, _).
list_n_fac([Z1|Zs], N0, Z0) :-
   Z1 #= Z0 * N0,
   N1 #= N0 + 1,
   list_n_fac(Zs, N1, Z1).

Sample query:

?- list_factorial(Zs, 8).
Zs = [1,2,6,24,120,720,5040,40320].

Here's the most general query:

?- list_factorial(Zs, N).
(  N = 0, Zs = [1]
;  N = 1, Zs = [1]
;  N = 2, Zs = [1,2]
;  N = 3, Zs = [1,2,6]
;  N = 4, Zs = [1,2,6,24]
;  N = 5, Zs = [1,2,6,24,120]
...

score 0 · Accepted Answer · answered Apr 13 '15 at 21:16

the minimal correction, indicating the main problem

insertList(H, L, [H|L]):- !.

factorial(0, 1, [1]).
factorial(N, F, Fs):- N1 is N-1, factorial(N1, F1, L), F is N * F1, insertList(F, L, Fs). 

list_factorial(X, L):- factorial(X, F, L).

but it will loop if you request backtracking after the first solution is returned. You could add the test @false suggested... otherwise, another definition could be

factorials(N, L) :-
    N > 0 -> L = [F,G|Fs], M is N-1, factorials(M, [G|Fs]), F is G*N ; L = [1].

score 0 · Answer 3 · answered Apr 15 '15 at 14:47

Another solution is:

factorial(0,1) :- !.
factorial(N,F) :- 
    N>0, N1 is N - 1, factorial(N1,F1), F is N * F1.

list_factorial(N,L) :-
    N>1, !, N2 is N-1, list_factorial(N2,L2), factorial(N,F), append(L2,[F],L). 
list_factorial(N,[F]) :- factorial(N,F).

I changed your factorial with the test if N is greater than 0, because you can't do the factorial of negative number and with a cut to get only one solution.

wvdz · Answer 4 · 2015-04-14T07:02:22.297

-1

You made me install SWI-prolog haha.

list_fact(N,M,A):- A is N * M.
list_fact(N,M,A):- N1 is N + 1, M1 is N * M, list_fact(N1,M1,A).

Call as

list_fact(1,1,A).

It's quite simple. The first rule calculates the next factorial as N * M. The second rule makes a recursive call where N = N + 1 and M = the previous factorial calculated in rule 1.

edited Apr 14 '15 at 07:02

answered Apr 13 '15 at 21:16

wvdz

16,251
4
53
90

@repeat Obviously I meant factorial. The algorithm is still correct. – wvdz Apr 14 '15 at 07:02
@repeat I guess you have a point there. I didn't realize he was looking for an actual list, so I just made a function that keeps generating factorials until it is terminated. – wvdz Apr 14 '15 at 11:13

List of factorials in Prolog

4 Answers4