Take the 2-minute tour ×

I'm trying to generate multiple permutations using this code:

:- use_module(library(clpfd)).

p(N, Indexes) :-
    M in 1..N,
    M #=< N,
    length(Indexes, M),
    Indexes ins 1..N.

It returns me all the results, but in the end crashes with ERROR: Out of global stack

share|improve this question
the condition 'M #=< N' is already implied by 'M in 1..N' –  CapelliC Mar 5 '12 at 6:55
Yes, but using the trace i saw prolog is not ending the loop so i thought that this could help, but it didn't –  Łukasz Mar 5 '12 at 8:48
add comment

3 Answers

up vote 3 down vote accepted

What happens in your code is that the length of the list is implicitly set by calling length/2. This will start with a list of length 0, which binds M to 0, which in turn wakes up the constraint M in 1..N, which fails. Next it returns a list of length 1, which succeeds, then on backtracking a list of length 2, which succeeds again. After that, any further backtracking into length/2 will return longer and longer lists, but waking M in 1..N will always fail until the list becomes so large that you run out of memory.

What you need to do is place the choicepoint before the length/2 call instead of inside of it by, e.g., replacing

M #=< N,

(which is a redundant constraint anyway) with


This gives you:

[debug] [1]  ?- p(2,I).
I = [_G3025],
_G3025 in 1..2 ;
I = [_G3102, _G3105],
_G3102 in 1..2,
_G3105 in 1..2.

[debug] [1]  ?- 
share|improve this answer
Thank you, it solved my problem, but I have trouble understanding why;) Dou you have any link to documentation why M becomes 0? I tried also ading M #>= which was also redundant and did not help. I thought that M ins 1..N is something like loop, but I assume it only becomes loop when we force it to be in the domain. –  Łukasz Mar 5 '12 at 9:06
@Łukasz: M starts from 0, as twinterer clearly (thanks! +1) explained. Try this query: ?- length(X,Y). –  CapelliC Mar 5 '12 at 10:21
@Łukasz: M ins 1..N is not a loop, it's a constraint that restricts the domain of M to be between 1 and N. As a constraint, it gets suspended until the bounds of M change, when it will be woken and check its consistency. length/2 is not a constraint, i.e., the domain of variable M is not taken into account. Calling length/2 with uninstantiated variables will have it return an empty list. This binds M to 0, which changes the bounds of M's domain and thus wakes the constraint posted on M. The constraint then checks it's consistency and fails, since 0 is not in the domain. –  twinterer Mar 5 '12 at 13:17
add comment

As twinterer already answered to question, I just add a simpler way to get (proper) permutations (could be useful?):

permutations_n(N, P) :-
  numlist(1, N, L),
  permutation(L, P).


?- permutations_n(3, X).
X = [1, 2, 3] ;
X = [1, 3, 2] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
share|improve this answer
add comment

It is not clear to me what you mean by multiple permutations. But probably your program shall start with between/3 and then contain an all_different/1 constraint.

p(N, Indices) :-
    between(1,N,M), % or maybe rather between(0,N,M).
    length(Indices, M),
    Indices ins 1..N,

And then, use labeling/2 to generate actual solutions.

share|improve this answer
+1 for better solution, not just fixing the bug. (should be Indices ins 1..N though) –  twinterer Mar 6 '12 at 7:25
@twinterer: Thank you, fixed! –  false Mar 6 '12 at 12:50
add comment

Your Answer


