2

あるリストが別のリストの順列であるかどうかを判断するプロローグ プログラムを作成しようとしています。入力は の形式で、 listが list の順列であるperm(L,M)場合にのみ true になります。LM

これは私の AI クラスのためのものなのでpermutation、gprolog が既に提供している気の利いた小さな述語をそのまま使用することはできません。私たちの教授は、member述語が役立つかもしれないと指摘しましたが、述語を含む私が持っているアイデアは、非常にトリッキーで、それほど宣言的ではないものを必要とするようです (そして、あまり高度にならずにこれを解決する方法があると思います.クラスはプロローグにとって新しいものです。)

とにかく、確認する方法の 1 つは、LとMが同じサイズであること、各L要素が にMあり、各M要素が にあることを確認することですL(! の使用がありmemberます)。[2,2,4]ただし、これはや などの場合には十分ではありません[4,4,2]。

別の方法としては、各要素の同じカウントが反対側のリストにあることを確認することもできますが、プロローグに関する私の印象では、あらゆる種類の変数「メモリ」はかなり難しいビジネスです (実際、私が見たサンプル プログラムはソートの実行などは、実際にはまったくデータを操作しているわけではありません。それらは単に「仮説的に」物事を再配置し、イエスかノーかを伝えているだけです...?)

精神的には、リストとチェック要素の両方を並べてソートすることもできますが、それは、他の多くの考え方の中で、オブジェクト指向すぎるように思えます...

ヒントはありますか？私の最大の問題は、（前述のように）「操作」を行うことは、それらについて尋ね、目的の場所に到達するのに十分長く物事が真実であり続けることを望んでいるように見えるという事実のようです.

**更新: gprolog はdelete機能を提供しますが、次のような試みを行うと、予想していた宣言関連の問題が発生します。

perm([LH|LT], R) :- member(LH,R), delete([LH|LT],LH,R), perm(LT,R).

マニュアルでは、delete は次のように定義されています。

実行：

{trace}
| ?- perm([1,2,3],[3,1,2]).
      1    1  Call: perm([1,2,3],[3,1,2]) ? 
      2    2  Call: member(1,[3,1,2]) ? 
      2    2  Exit: member(1,[3,1,2]) ? 
      3    2  Call: delete([1,2,3],1,[3,1,2]) ? 
      3    2  Fail: delete([1,2,3],1,[3,1,2]) ? 
      2    2  Redo: member(1,[3,1,2]) ? 
      2    2  Fail: member(1,[3,1,2]) ? 
      1    1  Fail: perm([1,2,3],[3,1,2]) ? 

(1 ms) no

**更新 2: 私はそれを理解したかもしれないと思います! ちょっと冗長ですが、かなりの数のケースでテストしましたが、まだ悪いケースは見つかりませんでした。誰かが大きな問題を見つけたら、指摘してください:

perm([],[]). 
perm([LH|LT],R) :- length([LH|LT],A), length(R,B), A == B, member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.
perm_recurse([],X).  %If we get here, all elements successfully matched
perm_recurse([LH|LT],R) :- member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.

私はカットオペレーターが好きです..

4

4 に答える 4

2

より一般的な述語を定義し、それを狭めた方法で使用することは常に良いことです:

perm(X,L):- mselect(X,L,[]).

mselect([A|B],L,R):- select(A,L,M), mselect(B,M,R).
mselect([],L,L).

member2 番目のリストが変更されないままになるため、適切ではありません。delete多重度を削除するので、どちらも良くありません。

でも使えappendます。:) それもピッキングと削除を組み合わせています:

perm([A|B],L):- length(L,N), between(0,N,I),length(X,I),
  append(X,[A],Y), append(Y,Z,L),
  append(X,Z,M), perm(B,M).
perm([],[]).
于 2013-07-04T19:16:30.617 に答える
2 
perm(L, M) :- sort(L, X), sort(M, X).

これにより、かなり近くなり、完全に宣言的になります（「2つのリストは、同じソート表現を持つ場合、相互の順列になります」が、Prologでソートすると重複が削除されます）。perm([1,2], [2,2,2,1])ただし、必要かどうかわからないような場合は成功します。ただし、[2,2,4] と [4,4,2] は両方とも にソートされるため、処理され[2,4]ます。別の解決策は次のようなものです。

perm([], []).
perm([L|Ls], M) :- select(L, M, Ms), !, perm(Ls, Ms).

このバージョンは [2,2,4] と [4,4,2] では成功しませんが、[1,2] と [2,2,2,1] では正しく失敗します。あなたがどちらを望んでいるのかはわかりませんが、おそらくどちらかが正しいと思います。

于 2013-07-04T16:58:00.887 に答える
1

従うべき通常のモデルは帰納的です。

N-1 要素のすべての順列を構築する方法を知っている場合、N 要素のすべての順列は、使用可能なすべての位置に要素を挿入して取得されます。

「トレードのトリック」は select/3 ビルトインを使用することです。これは、メンバーのように要素を「ピーク」しますが、リストから削除して小さいリストを「返します」。これらの動詞は、Prolog にはあまり適していません。select/3 が、要素、それを含むリスト、およびそれが欠落している同一のリストの間の関係であるとしましょう。

次に、すべての検索を Prolog に任せます...結果のコードは本当に小さいです...

于 2013-07-04T17:02:15.340 に答える
0

両方のリストを並べ替えて結果を比較するだけです

于 2013-07-05T12:06:46.963 に答える