2

我是 Prolog 世界的新手。我想知道一个排列是否是“一个周期”。

我正在尝试编写一个谓词来从排列中生成循环。这是我的代码（不工作）：

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).

排列由两个列表表示（例如：[1, 2, 3, 4], [3, 4, 2, 1]）。 find_next为元素 (E) 生成下一个循环元素 (N)（例如：E=1，N=3）。 find_cycle从元素 E 开始寻找循环 (C)。

不幸的是，当 find_next 返回与循环 C 的第一个元素相同的 N 时，我不知道如何停止重复。

编辑：一些例子。

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

应该返回：

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

和：

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

应该返回：

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

为什么？它是将排列简单地分解为不相交的循环。让我们分析第二个排列：[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.

这种排列不能分解成一个循环（生成循环的长度小于排列的长度）。

4

2 回答 2

2

要找到置换的所有循环：

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).

注释条款将删除循环列表的固定元素。

要仅获得一个循环排列，您可以将第三个参数限制为一个元素列表。例如：

?- 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]].
于 2012-12-17T18:51:05.857 回答
1

-嗨戴夫，这是我解决问题的方法。我按照你的指示，比如 1 到 4 ， 4 到 3 等等，这就是我想出的。首先，我在两个列表（排列）的元素之间创建弧线，然后我只需使用 find_cycle 在创建的图形中移动（直到我们的节点开始重复）。我尝试使用自我解释的变量名称，但如果很难理解代码，请告诉我。 

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).
于 2012-12-17T18:30:49.507 回答