@Will Ness already gave you a fine definition for perm/2
. But let's look at your program. In fact, you have very odd behavior: sometimes it seems to work, and sometimes not. How can we narrow that down? Tracing does not seem to be an option, as you have experienced yourself.
Here is a particular debugging technique, called slicing. I will modify your program a bit to see what is going on, by inserting goals false
. The resulting program is called a failure slice. And I will use the query:
?- mysort([1],[2|_]).
Fatal Error: global stack overflow
Clearly, a list with a single 1
as element cannot correspond to a list starting with 2
. So ideally, this should fail. And it cannot be that complex. Can it?
@larsmans gave you already a hint, but I will try it out myself. I will add the following goals false
into your program. In this manner certains parts will never be called, they are striked through. And certain predicates will not be called at all, so I will no longer show them:
?- mysort([1],[2|_]). mysort(L,M) :- backtrack_perm(L,M), false,sorted(M),!.backtrack_perm([],[]) :- false. backtrack_perm([LH|LT],R) :- length([LH|LT],A), length(R,B), false,A == B,member(LH,R),select(LH,[LH|LT],X),select(LH,R,Y),perm_recurse(X, Y).
This failure slice is in a sense, as bad as your program: Again, it does not terminate. But it is smaller. To fix the problem you have to do something in that fragment. For, as long as that part remains as is, the problem will persist.
In this case, it is the goal length(R,B)
which is the culprit: The variable B
occurs here for the first time, so it is uninstantiated. And also R
is uninstantiated. What are the answers for the goal length(R, B)
. Try it out!
| ?- length(R, B). B = 0 R = [] ? ; B = 1 R = [_] ? ; B = 2 R = [_,_] ? ; B = 3 R = [_,_,_] ? ; B = 4 R = [_,_,_,_] ? ; B = 5 R = [_,_,_,_,_] ? ...
So there are infinitely many answers. Therefore your program does not terminate.
This problem can be easily fixed by replacing length(R, B), A == B
by length(R, A)
.
| ?- mysort([9,1,2,3,4,5,6,7,8],L). L = [1,2,3,4,5,6,7,8,9] (21841 ms) yes
Some more remarks: The !
in your programs are red cuts, they might cause you a lot of trouble. And then, the execution time is not that great: 21 seconds for sorting 9 elements does not sound very cool. But please keep in mind that your description essentially says: I want a permutation, that is ascending. You do not say more than that. Given that very scarce information, Prolog is at least capable of finding the right answers. And it is even quite space efficient.
How to turn this program into a more efficient one, see this answer.