Permutation predicate in Prolog

Question

I have written the following in Prolog (I am using version 7.4.0-rc1), trying to define a predicate insertPermutation/2 which is true if and only if both arguments are lists, one a permutation of the other.

delete(X,[X|T],T). % Base case, element equals head.
delete(X,[A|B],[A|C]) :- delete(X,B,C). % And/or repeat for the tail.

insert(X,Y,Z) :- delete(X,Z,Y). % Inserting is deletion in reverse.

insertPermutation([],[]). % Base case.
insertPermutation([H|T],P) :- insertPermutation(Q,T), insert(H,Q,P). % P permutation of T, H inserted.

I have already been made aware that delete is not a good name for the above helper predicate. We are required to write these predicates, and we cannot use the built-in predicates. This is why I wrote the above code in this way, and I chose the name I did (because I first wrote it to delete an element). It is true if and only if the third argument is a list, equal to the list in the second argument with the first instance of the first argument removed.

The insertPermutation predicate recursively tests if P equals a permutation of the tail of the first list, with the head added in any position in the permutation. This way it works to the base case of both being empty lists.

However, the permutation predicate does not behave the way I want it to. For instance, to the query

?- insertPermutation([1,2,2],[1,2,3]).

Prolog does not return false, but freezes. To the query

?- insertPermutation(X,[a,b,c]).

Prolog responds with

X = [a, b, c] ;
X = [b, a, c] ;
X = [c, a, b] ;
X = [a, c, b] ;
X = [b, c, a] ;
X = [c, b, a] ;

after which it freezes again. I see these problems are related, but not how. Can someone point out what case I am missing?

Edit: Two things, this is homework, and I need to solve this problem using an insert predicate. I wrote this one.

Why don't you look at how Prolog does it? See permutation/2 The idea is to convert both versions to a canonical form then compare. If they have the same canonical form then they can be a permutation of each other or identical to each other. — Guy Coder
For this problem I am required to use a function that inserts an element, that is why! I have already written an alternative definition that does work, but cannot get it to work using the insert predicate. — Kermit
You should say that in the question and if it is homework say so. — Guy Coder
First thing you should do is to rename your predicates so that they are not the same name as the standards ones. e.g. change permutation to my_permutation, etc. Then you should use either trace or gtrace. — Guy Coder

Kermit Kermit · Accepted Answer · 2017-03-29T20:21:05

The answer is to change the last line

% P permutation of T, H inserted.
insertPermutation([H|T],P) :- 
    insertPermutation(Q,T), 
    insert(H,Q,P).

% P permutation of T, H inserted.
insertPermutation(P,[H|T]) :- 
    insertPermutation(Q,T), 
    insert(H,Q,P).

The use cases only needed to check if the first element is a permutation of the latter, not the other way around (or vice versa). Anti-climatic, but the answer to my problem.

Permutation predicate in Prolog

1 Answers