CODEWITHSUNDEEP
prologpermutationcycle
Dave
Dave

Reputation: 473

Find cycle of permutation in Prolog

I'm new in Prolog world. I want to find out if a permutation is 'one-cycle'.

I'm trying to write a predicate to generate cycle from permutation. Here is my code (not working):

find_next([E|_], [N|_], E, N).

find_next([_|L1], [_|L2], E, N) :-
  find_next(L1, L2, E, N).


find_cycle(L1, L2, E, C) :-
    append(C, [E], C1),
    find_next(L1, L2, E, N),
    find_cycle(L1, L2, N, C1).

Permutations are represented by two lists (for example: [1, 2, 3, 4], [3, 4, 2, 1]). find_next generates next cycle element (N) for element (E) (for example: E=1, N=3). find_cycle looks for cycle (C) starting from element E.

Unfortunately I don't know how to stop my recurrence when find_next returns N same as first element of cycle C.

EDIT: some examples.

find_cycle([1, 2, 3, 4], [3, 4, 2, 1], 1, X).

should return:

X = [1, 3, 2, 4];
false.

and:

find_cycle([1, 2, 3, 4], [4, 2, 1, 3], 1, X).

should return:

X = [1, 4, 3];
false.

Why? It is simple decomposition of permutation into disjointed cycles. Let's analyze second permutation: [1, 2, 3, 4], [4, 2, 1, 3].

Take first element: 1.
1 goes into 4
4 goes into 3
3 goes into 1
end of cycle.

This permutation is not decomposable into one cycle (length of generated cycle is smaller than length of permutation).

Upvotes: 2

Views: 737

Answers (2)

gusbro
gusbro

Reputation: 22585

To find all the cycles of the permutation:

perm_to_cycles(Perm, NPerm, Cycles):-
  perm_struct(Perm, NPerm, PermS),
  perm_to_cycles(PermS, [], [], Cycles),
  !.

perm_to_cycles([], _, Cycles, Cycles).
%perm_to_cycles([p(Id, Id)|PermS], _, InCycles, Cycles):-
%  perm_to_cycles(PermS, [], InCycles, Cycles).  % This clause would remove fixed elements
perm_to_cycles([p(Id, Item)|PermS], Cycle, InCycles, Cycles):-
  (select(p(Item, NId), PermS, NPermS) ->
    perm_to_cycles([p(Item, NId)|NPermS], [Id|Cycle], InCycles, Cycles) ;
    (
      reverse([Id|Cycle], RCycle),
      perm_to_cycles(PermS, [], [RCycle|InCycles], Cycles)
    )
  ).

perm_struct([], [], []).
perm_struct([Item|Perm], [NItem|NPerm], [p(Item, NItem)|PermS]):-
  perm_struct(Perm, NPerm, PermS).

The commented clause would remove fixed elements of list of cycles.

To get only one-cycle permutations you can constrain the third argument to be a one-element list. For example:

?- perm_to_cycles([1, 2, 3, 4], [3, 4, 2, 1], [X]).
  X = [1, 3, 2, 4]
?- perm_to_cycles([1, 2, 3, 4], [4, 2, 1, 3], [X]).
  false.
?- perm_to_cycles([1, 2, 3, 4], [4, 2, 1, 3], X).
  X = X = [[2], [1, 4, 3]].

Upvotes: 2

ssbarbee
ssbarbee

Reputation: 1712

-Hi Dave, here is my solution to the problem. I followed your instructions like 1 goes to 4 , 4 goes to 3 etc and here is what I came up with. First I create arcs between the elements of the two lists(permutations) and then I simply move through the created graph using find_cycle (until our nodes start repeating ). I tried to use variable names that are self explanatory but if have hard time understanding the code let me know. 

create_arcs([],[],[]).
create_arcs([H|T],[H1|T1],[arc(H,H1)|RezArc]) :- create_arcs(T,T1,RezArc).

find_cycle(Perm,Perm2,E,X) :- create_arcs(Perm,Perm2,Arcs),
                              find_cycle(E,Arcs,[],X).

find_cycle(StartNode,Arcs,LocRez,LocRez) :-   member(arc(StartNode,NextNode),Arcs),
                                              member(StartNode,LocRez).

find_cycle(StartNode,Arcs,LocRez,FinalRez) :- member(arc(StartNode,NextNode),Arcs),
                                              not(member(StartNode,LocRez)),
                                              append(LocRez,[StartNode],LocRezNew),
                                              find_cycle(NextNode,Arcs,LocRezNew,FinalRez).

Upvotes: 1

Related Questions