How to remove variants from a List? Prolog

2
votes

I am trying to write a predicate removeRotations. The idea is that I have a List of the following form:

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

It takes each element, rotates it using append(T,[H],Rotation)
It then checks the rotation if it is a member of the whole list. If Yes, then it is removed from the List using

select(Rotation,[H|T],NewList)

Similarly, the same is going to happen to the remaining List. In the end it should return the List that has no rotations.

Going through each H of List    Rotation        Stays/Remove  
    [1,2,3]                      [2,3,1]     [1,2,3] Stays ([2,3,1] not in List)
    [2,1,3]                      [1,3,2]         Remove [1,3,2]
    [1,3,2]                      [3,2,1]         Remove [3,2,1]
    [3,1,2]                      [1,2,3]         Remove [1,2,3]
    [3,2,1]                      [2,1,3]         Remove [2,1,3]

?-removeRotations([[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],List).
List = [[3,1,2]]
?-removeRotations([[1, 2, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],List).
List = [[1,3,2],[3,1,2]]

My attempt is just bad, I am unsure what to do when H is not a member?

rr([H|T],[H1|T1],W):-
    r([H|T],[H1|T1],W).
r([],_,[]):-!.
r([H|T],[H1|T1],[W|L]):-
    r1(H,[H1|T1],W),
    r(T,[H1|T1],L).

r1([H|T],[H2|T2],W):-
    append(T,[H],Rot),
    (\+member(Rot,[H2|T2])->  W=[];select(Rot,[H2|T2],W)).

?-rr([[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],[[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],W).
W = [[], [[1, 2, 3], [2, 1, 3], [3, 1, 2], [3, 2, 1]], [[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2]], [[2, 1, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]], [[1, 2, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]]]
false

Any help will be appreciated.

2
prolog

2 Answers

2
votes

If I understood correctly you want to apply a transformation (rotation) on elements of a list and remove all the originals where the transformation appears within the list.

Ok, simplest approach: hold one unaltered list as reference. Go through each element of the list and put it in the return list if and only if its tranformation does not appear within the original list.

removeRotations(In, Out):-
    remRot(In,In,Out).

rot([H|T],Rot):-
    append(T,[H],Rot).

remRot([],_,[]).
remRot([H|T],L1,[H|L]):-
    rot(H,Rot),
    \+ member(Rot,L1),
    !,
    remRot(T,L1,L).
remRot([H|T],L1,L):-
    rot(H,Rot),
    member(Rot,L1),
    remRot(T,L1,L).

?- removeRotations([[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],W).
W = [[1, 2, 3]] ;
false.

Ok, in case you want to remove all transformations you look for the inverse transformation: an element is kept in the list if its inversed transformation is not a member of the list. You only need to alter the rot/2 part:

rot(L,[H|Tmp]):-
    append(Tmp,[H],L).

?- removeRotations([[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],W).
W = [[3, 1, 2]] ;
false.

?- removeRotations([[1, 2, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1]],W).
W = [[1, 3, 2], [3, 1, 2]] ;
false.
2
votes

I am not sure which rotation you want to keep and which you want to remove, but this will return a list which has no rotations(of any length, not just 1).

rotation(X, Y) :-
    append(P, S, X),
    append(S, P, Y).

remove_rotations(Xs, Ys) :-
    remove_rotations(Xs, [], Ys).
remove_rotations([], Acc, Ys) :- reverse(Acc, Ys).
remove_rotations([X|Xs], Acc, Ys) :-
    exclude(rotation(X), Xs, Xs1), % exclude/3 from swi-prolog
    remove_rotations(Xs1, [X|Acc], Ys).

findall(P, permutation(P, [1,2,3,4]), Ps), remove_rotations(Ps, X), print(X).
[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,4,2,3],[1,3,4,2],[1,4,3,2]]