4

これが私の最初のアイデアです。 

perm([X|Y],Z) :- takeout(X,Z,W), perm(Y, W).   
perm([],[]).

を実行しようとすると-? perm([1, 2, 3], P).、スタックオーバーフローの問題が発生しました。

ただし、2つのステートメントの順序を変更すると、機能します。 

perm([X|Y],Z) :- perm(Y, W), takeout(X,Z,W).  
perm([],[]).

なんで？私はPrologの初心者です。助けてください。

4

4 に答える 4

2

あなたtakeout/3が参照するものは、一般的に次のように知られていますselect(X, Xs0, Xs)

ここに別の定義があります - DCG の珍しい使用法を説明するためです。

perm(Xs,Ys) :-
   phrase(perm(Xs),[],Ys).

perm([]) --> [].
perm([X|Xs]) --> perm(Xs), ins(X).

ins(X),[X] --> [].
ins(X),[Y] --> [Y], ins(X).
于 2011-11-11T14:22:10.870 に答える
0

PrologはSLD解決を使用するため、句の順序と句内のリテラルの順序に違いがあります。基本的に、エンジンは深さ優先方式で上から下に検索することにより、句の先頭を解決しようとします。言い換えると、宣言型セマンティクスの上に手続き型セマンティクスがあります。この区別は初心者を混乱させることがありますが、一方で、Prologが本当にプログラミング言語である（つまりチューリング完全である）主な理由です。

于 2012-02-07T23:02:30.797 に答える
0

さて、takeout述語は次のようになります。

takeout( X, [X|R], R ).
takeout( X, [F|R], [F|S] ) :-
    takeout( X, R, S ).

SWI-Prolog には、 という便利な述語がありtraceます。

最初のケース:

X = [1, 2, 3] ;
   Redo: (10) takeout(3, _G477, _G485) ? creep
   Call: (11) takeout(3, _G480, _G483) ? creep
   Exit: (11) takeout(3, [3|_G483], _G483) ? creep
   Exit: (10) takeout(3, [_G479, 3|_G483], [_G479|_G483]) ? creep
   Call: (10) perm([], [_G479|_G483]) ? creep
   Fail: (10) perm([], [_G479|_G483]) ? creep
   Redo: (11) takeout(3, _G480, _G483) ? creep
   Call: (12) takeout(3, _G486, _G489) ? creep
   Exit: (12) takeout(3, [3|_G489], _G489) ? creep
   Exit: (11) takeout(3, [_G485, 3|_G489], [_G485|_G489]) ? creep
   Exit: (10) takeout(3, [_G479, _G485, 3|_G489], [_G479, _G485|_G489]) ? creep
   Call: (10) perm([], [_G479, _G485|_G489]) ? creep
   Fail: (10) perm([], [_G479, _G485|_G489]) ? creep
   Redo: (12) takeout(3, _G486, _G489) ? creep
   Call: (13) takeout(3, _G492, _G495) ? creep
   Exit: (13) takeout(3, [3|_G495], _G495) ? creep
   Exit: (12) takeout(3, [_G491, 3|_G495], [_G491|_G495]) ? creep
   Exit: (11) takeout(3, [_G485, _G491, 3|_G495], [_G485, _G491|_G495]) ? creep
   Exit: (10) takeout(3, [_G479, _G485, _G491, 3|_G495], [_G479, _G485, _G491|_G495]) ? creep
   Call: (10) perm([], [_G479, _G485, _G491|_G495]) ? creep
   Fail: (10) perm([], [_G479, _G485, _G491|_G495]) ? creep
   Redo: (13) takeout(3, _G492, _G495) ? creep
   Call: (14) takeout(3, _G498, _G501) ? creep
   Exit: (14) takeout(3, [3|_G501], _G501) ? creep
   Exit: (13) takeout(3, [_G497, 3|_G501], [_G497|_G501]) ? creep
   Exit: (12) takeout(3, [_G491, _G497, 3|_G501], [_G491, _G497|_G501]) ? creep
   Exit: (11) takeout(3, [_G485, _G491, _G497, 3|_G501], [_G485, _G491, _G497|_G501]) ? creep

2 番目のケースでは:

X = [1, 2, 3] ;
   Redo: (8) takeout(1, _G451, [2, 3]) ? creep
   Call: (9) takeout(1, _G532, [3]) ? creep
   Exit: (9) takeout(1, [1, 3], [3]) ? creep
   Exit: (8) takeout(1, [2, 1, 3], [2, 3]) ? creep
   Exit: (7) perm([1, 2, 3], [2, 1, 3]) ? creep

したがって、述語列挙の順序は実際には重要です。最初のケースでは、未知の値を持つ多くの状態を生成しました。trace紙のリストを作成し、実際に何が起こっているかを実行して描画することは (可能な限り) 良い考えです。

takeoutしかし簡単に言えば、最初のケースでは、事実で覆われた多くの未知の変数を生成していますperm。

于 2011-11-09T20:51:06.480 に答える
-1

ベースケースのperm（[]、[]）を最初に表示する必要があります。そうしないと、スタックスペースがなくなるまでperm述語に下降し続けます。将来の述語についてもそれを覚えておいてください。これはプロローグで非常に重要です。

また、おそらく他の述語でパーマとテイクアウトの順序を切り替える必要があります。

于 2011-11-09T21:20:40.973 に答える