CODEWITHSUNDEEP
prolog
S0rin
S0rin

Reputation: 1293

Prolog permutations of size M - ERROR: Out of global stack

I want this code to output permutations (with repetition) of the letters a, b, and c. 

letter('a').
letter('b').
letter('c').

f(0,L,L).

f(N,L0,L):-
  append(L0,[X],L1),
  letter(X),
  N1 is N-1,
  f(N1,L1,L).

f(N,L):-
  f(N,[],L).

When I execute it like so

?- f(3,L).
L = [a, a, a] ;

The first answer is correct, but when I try to backtrack for more answers I receive the error:

ERROR: Out of global stack

I can see that the error is because my counter N is decremented from 0 to - 1 when backtracking, but I thought the interpreter would backtrack to when N was positive, thus preventing this from happening.

Can anyone explain what is going wrong? Thanks

Upvotes: 0

Views: 82

Answers (1)

lurker
lurker

Reputation: 58304

Your recursive call to f/3 occurs with ever-decreasing values of N without ever checking that it is non-negative. Try:

f(N, L0, L):-
    N >= 0,              % add this
    append(L0, [X], L1),
    letter(X),
    N1 is N-1,
    f(N1, L1, L).

Upvotes: 2

Related Questions