Permutation of a list where numbers must change its position in Prolog

Question

I'm trying to solve this question for my assignment.

The predicate acceptable_permutation(L,R) should succeed only if R represents an acceptable permutation of the list L. For example: [2,1,3] is not an acceptable permutation of the list [1,2,3] because 3 did not change its position.

The outputs are supposed to be like this:

?- acceptable_permutation([1,2,3],R).
R = [2,3,1] ;
R = [3,1,2] ;
false

?- acceptable_permutation([1,2,3,4],R).
R = [2,1,4,3] ;
R = [2,3,4,1] ;
R = [2,4,1,3] ;
R = [3,1,4,2] ;
R = [3,4,1,2] ;
R = [3,4,2,1] ;
R = [4,1,2,3] ;
R = [4,3,1,2] ;
R = [4,3,2,1] ;
false.

My outputs of my code however gives:

?- acceptable_permutation([1,2,3],R).
R = [1,2,3] ;
R = [1,3,2] ;
R = [2,1,3] ;
R = [2,3,1] ;
R = [3,1,2] ;
R = [3,2,1] ;

?- acceptable_permutation([1,2,3,4],R).
R = [1,2,3,4] ;
R = [1,2,4,3] ;
R = [1,3,2,4] ;
R = [1,3,4,2] ;
R = [1,4,2,3] ;
R = [1,4,3,2] ;
R = [2,1,3,4] ;
R = [2,1,4,3] ;
R = [2,3,1,4] ;
R = [2,3,4,1] ;
R = [2,4,1,3] ;
R = [2,4,3,1] ;
R = [3,1,2,4] ;
R = [3,1,4,2] ;
R = [3,2,1,4] ;
R = [3,2,4,1] ;
R = [3,4,1,2] ;
R = [3,4,2,1] ;
R = [4,1,2,3] ;
R = [4,1,3,2] ;
R = [4,2,1,3] ;
R = [4,2,3,1] ;
R = [4,3,1,2] ;
R = [4,3,2,1] ;
false.

My code is the following:

acceptable_permutation(list,list).

del(symbol,list,list).

del(X,[X|L1], L1).

del(X,[Y|L1], [Y|L2]):-
    del(X,L1, L2).
    acceptable_permutation([] , []).

acceptable_permutation(L, [X|P]):-
    del(X, L, L1),
    acceptable_permutation(L1, P).

Please tell me where exactly the problem is, so that my outputs should match the correct outputs. I would appreciate a lot if you show me how exactly it is done.

Answer 1

1) A permutation that has no fixed points is called derangement. A funny name! TIL that, too.

2) Like this previous answer, we use maplist/3 and permutation/2.

3) Unlike this previous answer, we use prolog-dif instead of (\=)/2 to preserve logical purity.

logical-purity helps keep Prolog programs general, and—in this case—also increase efficiency.

Let's define list_derangement/2 like so:

list_derangement(Es, Xs) :-
   maplist(dif, Es, Xs),         % using dif/2
   permutation(Es, Xs).

Note that the maplist/2 goal now precedes the other one!

This can speed up the detection of failing cases, compared to find_perm/2 from previous answer:

?- time(find_perm([1,2,3,4,5,6,7,8,9,10,11],
                  [_,_,_,_,_,_,_,_,_, _,11])).
% 303,403,801 inferences, 37.018 CPU in 37.364 seconds (99% CPU, 8196109 Lips)  
false.

?- time(list_derangement([1,2,3,4,5,6,7,8,9,10,11], 
                         [_,_,_,_,_,_,_,_,_, _,11])).
% 15,398 inferences, 0.009 CPU in 0.013 seconds (67% CPU, 1720831 Lips)         
false.

For corresponding ground terms above implementations are of comparable speed:

?- time((find_perm([1,2,3,4,5,6,7,8,9,10,11],_),false)).
% 931,088,992 inferences, 107.320 CPU in 107.816 seconds (100% CPU, 8675793 Lips)
false.

?- time((list_derangement([1,2,3,4,5,6,7,8,9,10,11],_),false)).
% 1,368,212,629 inferences, 97.890 CPU in 98.019 seconds (100% CPU, 13976991 Lips)
false.

Answer 2

The problem is that you don't check that all the elements of the output list are in a different position than the input list. You should add a predicate to check this, like that:

perm(L,LO):-
    acceptable_permutation(L,LO),
    different_place(L,LO).

different_place([A|T0],[B|T1]):-
    A \= B,
    different_place(T0,T1).
different_place([],[]).

?- perm([1,2,3],R).
R = [2, 3, 1]
R = [3, 1, 2]
false

Improvement 1: instead of creating your own predicate (in this case, different_place/2), you can use maplist/3 with \=/2 in this way:

perm(L,LO):-
    acceptable_permutation(L,LO),
    maplist(\=,L,LO).

Improvement 2: swi prolog offers the predicate permutation/2 that computes the permutations of a list. So you can solve your problem with only three lines:

find_perm(L,LO):-
    permutation(L,LO),
    maplist(\=,L,LO).

?- find_perm([1,2,3],L).
L = [2, 3, 1]
L = [3, 1, 2]
false