2

私はプロローグの世界で初めてです。順列が「1サイクル」かどうかを調べたい。

順列からサイクルを生成する述語を書こうとしています。これが私のコードです（動作していません）：

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

順列は 2 つのリストで表されます (例: [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.

なんで？これは、バラバラなサイクルへの順列の単純な分解です。2 番目の順列を分析してみましょう: [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.

この順列は、1 つのサイクルに分解できません (生成されるサイクルの長さは、順列の長さよりも短くなります)。

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

コメントされた句は、サイクルのリストの固定要素を削除します。

1サイクルの順列のみを取得するには、3番目の引数を1要素のリストに制限できます。例えば：

?- 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 に、などの指示に従いました。ここに私が思いついたものがあります。最初に、2 つのリスト (順列) の要素間に円弧を作成し、次に、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 に答える