gprolog-あるリストが別のリストの置換かどうかを判断する簡単な方法




gprolog manual (4)

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

これは私のAIクラス用ですので、gprologが既に提供している素敵な小さなpermutation述語を使うことはできません。 私たちの教授は、 member述語は有用かもしれないと指摘しましたが、私が関与しているアイデアは非常にトリッキーで宣言的なものを必要とするようです(そして、これを解決する方法があると仮定しています。クラスはプロローグの新機能です)。

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

もう1つの方法は、各要素の同じカウントが反対のリストにあることを保証することですが、プロローグの印象は、あらゆる種類の変数 'メモリ'がむしろ難しいということです(実際には、ソートを実行するなど、データを実際に操作しているわけではなく、単に「仮説的に」並べ替えてから、はい、いいえを教えていますか?)

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

何かヒント? 私の最大の問題は、(言及したように)「操作」をすることは、それらについて尋ねることや、物事があなたが望むところに到達するのに十分長い間真実を保つことを望むように思えるということです。

**アップデート:gprologはdelete機能を提供していますが、これは次のような試みで、私が期待していた宣言的な問題があります:

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

"delete(List1、Element、List2)はList1のElementのすべての出現を削除してList2を提供します。厳密な等号が必要です、cf.(==)/ 2"

実行:

{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), !.  

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


より一般的な述語を定義し、それを狭めた形で使うには、常に良いです:

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

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

memberは2番目のリストを変更しないままにしておくといいです。 それは多重度を削除するので、どちらも良いことではありません。

あなたはappend使用することができ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([],[]).

perm(L, M) :- sort(L, X), sort(M, X).

これはあなたをかなり近くにして、完全に宣言的です(「2つのリストは、同じソートされた表現を持つ場合、互いの順列ですが、Prologでソートすると重複が取り除かれます)。 しかし、 perm([1,2], [2,2,2,1])ように、あなたが望むかどうか分からない場合は成功します。 彼らは[2,4]分類されているので、[2,2,4]と[4,4,2]は扱います。 もう1つの解決策は次のようなものです:

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

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


従うべき通常のモデルは帰納的である

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

'trade of trick'はselect / 3組み込み関数を使用しています。つまり、メンバのように 'peek'要素を削除しますが、リストから削除し、小さなリストを返します。 これらの動詞はPrologには本当に適切ではありません。 select / 3は、要素とそれを含むリストと、それが欠けている同一のリストとの間の関係であるとしましょう。

そして、Prologにすべての検索をさせてください...結果のコードは本当に小さいです...


両方のリストをソートして結果を比較するだけです