6

リストを比較しようとしています。与えられた function(List1,List2) で、List1 の長さは N、List 2 の長さは M で、N>M です。

List2 の順列がたまたま List1 の最初の M 文字であるかどうかを確認したいと思います。

例えば、

predicate([a,c,b,d,e],[a,b,c,d]).

真であるべきであり、

predicate([a,c,b,e,d],[a,b,c,d]).

false にする必要があります。

ありがとうございました。

4

3 に答える 3

4

リスト間の関係を説明するときによくあることですが、この場合は DCG が便利です。

perm_prefix(Ls1, Ls2) :- phrase(perm(Ls2), Ls1, _).

perm([])  --> [].
perm(Ls0) --> [L], { select(L, Ls0, Ls1) }, perm(Ls1).

サンプルケース:

?- perm_prefix([a,c,b,d,e],[a,b,c,d]).
true

?- perm_prefix([a,c,b,e,d],[a,b,c,d]).
false.
于 2011-12-04T23:52:52.060 に答える
2

permutation/2および述語を使用すると、次のprefix/2ように記述できます。

has_prefix_perm(List1, List2) :-
    permutation(List2, Permutation),
    prefix(Permutation, List1),
    !.

補足として、 swi-prolog マニュアルを引用するには:

長さ N のリストには N があることに注意してください! 順列と無制限の順列生成は、かなり短いリスト (10! = 3,628,800) であっても、法外に高価になります。

したがってhas_prefix_perm/2、すべてのケースがテストされるため、特にプレフィックスモジュロ順列ではない場合は、長すぎる2番目のリストで呼び出さないように注意します。

もう 1 つの方法は、List2 が空になるまで List1 の項目が L​​ist2 のメンバーであるかどうかをテストすることです。これにより、順列が存在することがわかります。

has_prefix_perm(_, []) :- !.
has_prefix_perm([Head1|List1], List2) :-
    once(select(Head1, List2, Rest)),
    has_prefix_perm(List1, Rest).

そのように書かれているので、非根拠リストでは使用しませんが、あなたのOPを見て、それ以上検索しませんでした...

もう 1 つの方法は、 List1 が List2 の長さに短縮されているかどうかを確認することです。これは List2 の順列です。

has_prefix_perm(List1, List2) :-
    length(List2, L),
    length(LittleL1, L),
    append(LittleL1, _, List1),
    permutation(LittleL1, List2),
    !.

別の方法は...それを行う方法はたくさんあると思いますが、それほど複雑ではなく、あなたのスタイルに合った方法を選んでください! :)

個人的には最後の方に行きたいです。

于 2011-12-04T23:20:11.463 に答える
2

別の DCG ソリューションを次に示します。

perm(Xs,Ys) :- フレーズ(perm(Xs),[],Ys).

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

ins(X),[X]-->[].
ins(X),[Y]-->[Y],ins(X)。

帰属:プロローグの瞬間、展示 0

于 2012-11-08T18:20:17.730 に答える