CODEWITHSUNDEEP
prologpermutation
Barrett
Barrett

Reputation: 23

Prolog Permutations with Condition for Multiple Elements

I have a program to generate all the permutations of a list where for each 2<=i<=n, there is a 1<=j<i where |v(i)-v(j)|=1

For example, for [1,2,3], the results are:

[1,2,3]
[2,1,3]
[2,3,1]
[3,2,1]

[1,3,2] and [3,1,2] would be wrong because |3-1| and |1-3| are not 1

The code is:

takeout([X|T],X,T).
takeout([H|L],X,[H|T]) :-
    takeout(L,X,T).

takeout1([X|T],P,X,T) :-
    D is abs(X-P),
    D =:= 1.
takeout1([H|L],N,X,[H|T]) :-
    takeout1(L,N,X,T).

perm1([],[]).
perm1(L,[E|T]) :-
    takeout(L,E,R),
    perm_abs(R,E,T).

perm_abs([],_,[]).
perm_abs(L,O,[E|T]) :-
    takeout1(L,O,E,R),
    perm_abs(R,E,T).

perm(N,R):-
    numlist(1,N,L),
    perm1(L,R).

This code gives only the consecutive results. I think I am supposed to change something at takeout1, but I do not know where exactly.

Thank you in advance.

Upvotes: 0

Views: 146

Answers (1)

CapelliC
CapelliC

Reputation: 60034

valid(R) :-
    forall((nth1(I,R,X), I>1), (nth1(J,R,Y), J<I, 1 =:= abs(X-Y))).

?- forall((N=4, numlist(1,N,L), permutation(L,R), valid(R)),writeln(R)).
[1,2,3,4]
[2,1,3,4]
[2,3,1,4]
[2,3,4,1]
[3,2,1,4]
[3,2,4,1]
[3,4,2,1]
[4,3,2,1]
true.

You can add valid/1 after the intermediate permutation step, to get early filtering of invalid configurations.

Upvotes: 1

Related Questions