3

私はプロローグが初めてです。

リスト内の最小要素を見つけて削除する述語を書くのに助けが必要です。

どうもありがとうございました！

4

3 に答える 3

2

すべてのリスト項目が整数の場合、を使用できます!

:- use_module(library(clpfd)).

、、 、およびzmin_deleted/2を使用して定義します。maplist/2(#=<)/2same_length/2select/3

zmin_deleted(Zs1,Zs0) :-
   same_length(Zs1,[_|Zs0]),
   maplist(#=<(Min),Zs1),
   select(Min,Zs1,Zs0).

サンプルクエリ:

?- zmin_deleted([3,2,7,8],Zs).
  Zs = [3,7,8]
; false.

?- zmin_deleted([3,2,7,8,2],Zs).
  Zs = [3,  7,8,2]
; Zs = [3,2,7,8  ]
; false.

zmin_deleted/2「他の方向」でも機能することに注意してください。

?- zmin_deleted(Zs,[3,2,7,8]).
  _A in inf..2, Zs = [_A, 3, 2, 7, 8]
; _A in inf..2, Zs = [ 3,_A, 2, 7, 8]
; _A in inf..2, Zs = [ 3, 2,_A, 7, 8]
; _A in inf..2, Zs = [ 3, 2, 7,_A, 8]
; _A in inf..2, Zs = [ 3, 2, 7, 8,_A]
; false.
于 2015-08-05T06:28:02.030 に答える
1

ググらせてください。

最小限のリストをどのように見つけることができますか。.

とにかくいいmin_list述語がある。

?- min_list([1,2,2,3],X).
X = 1.

リストからいくつかの要素を削除する方法の小さな例を次に示します (すべて2の s がなくなっていることに注意してください)。

?- delete([1,2,2,3],2,X).
X = [1, 3].

要素の最初の機会のみを削除する場合は、次を使用しますselect。

?- select(2, [2,1,2,2,3], X), !.
X = [1, 2, 2, 3].

したがって、最終的な答えは次のようになります。

delete_min(A, C) :-
  min_list(A, B),
  select(B, A, C), !.

と

?- delete_min([1,1,2,3],X).
X = [1, 2, 3].
于 2013-01-15T15:14:15.463 に答える
0

繰り返しますが、リストに対して構造的再帰を使用してください。リストはノードで構築され[H|T]ます。つまり、head、H、およびtailの2 つのフィールドを持つ複合データ構造Tです。ヘッドは、ノードに保持されているデータ (リスト要素) でTあり、リストの残りの部分です。

追加のデータを保持しながら、リストに沿ってローリングすることで最小要素を見つけます-これまでに見たすべての最小要素:

minimum_elt([H|T],X):- minimum_elt(T,H,X).

空のリストの場合の定義はありません。空のリストには最小要素がありません。

minimum_elt([],X,X).

リストにそれ以上要素がない場合は、これまでの要素が答えです。

minimum_elt([A|B],M,X):-

ここに 2 つのケース: A < M、またはそうでない場合:

    A < M, minimum_elt(B,A,X).

minimum_elt([A|B],M,X):- 

    A >= M, minimum_elt(B,M,X).

これ以上言うことはありませんので、これでプログラムは完了です。

編集：ただし、その要素も削除したかった. これは物事を変えます。うーん。明らかなアプローチの 1 つは、まず最小の elt を見つけてから削除することです。すべての要素をもう一度比較する必要があります。今回は、以前に見つかった最小要素と比較します。これを 1 回のスキャンで実行できますか?

Lisp では可能でした。リストから要素を削除するには、外科的に、前のノードのテール ポインターをリセットして、削除されたノードの次のノードを指すようにします。次に、このアプローチを使用して、入力リストを 1 回スキャンし、前のノードへの参照をこれまでに見つかった最小要素に保持し、より小さい要素を見つけるたびにそれを交換します。次に、リストの最後に到達したら、最小限のノードを外科的に削除します。

しかし、Prolog では、リセットすることはできません。Prolog はセット ワンス言語です。つまり、リストを 2 回渡す必要があることに行き詰まっているように見えます... または、それについて非常に賢くなり、新しい候補が見つかるたびにそれらを並べ替えながら、可能なすべてのリストを構築することができます。最小の要素。

rem_min([A|B],L):-
    % two possibilities: A is or isn't the minimum elt
    rem_min(B,A,([A|Z],Z,Z),L).

rem_min([],A,(With,Without,Tail),L):- Tail = [],
    % A is indeed the minimal element
    L = Without.

rem_min([H|T],A,(With,Without,Tail),L):- H >= A, Tail=[H|Z],
    rem_min(T,A,(With,Without,Z),L).

rem_min([H|T],A,(With,Without,Tail),L):- H < A,  % use this H
    copy_the_list(With,Tail,W2,T2),              % no good - quadratic behaviour
    Tail=[H|Z], T2=Z,
    rem_min(T,A,(With,W2,Z),L).

copy_the_list([A|B],T,[A|C],C):- var(B), !, T=B.            % fresh tail
copy_the_list([A|B],T,[A|C],T2):- copy_the_list(B,T,C,T2).

したがって、2 番目のパスを避けることはできないようですが、少なくとも余分な比較をすべて保存できます。

rem_min([A|B],L):- N=[A|_], rem_min(B,A,N,[N|Z],Z,L).

rem_min([],_A,N,L2,Z,L):- Z=[], N=[_,1], % finalize the minimal entry
    scan(L2,L).
rem_min([H|T],A,N,L2,Z,L):- H >= A, Z=[H|Z2], rem_min(T,A,N,L2,Z2,L).
rem_min([H|T],A,N,L2,Z,L):- H < A,       % use this H
    N2=[H|_], N=[_],                     % finalize the non-minimal entry
    Z=[N2|Z2], rem_min(T,H,N2,L2,Z2,L).

scan( [], []).
scan( [[_,1]|B],C):- !, scan(B,C).       % step over the minimal element
scan( [[A]|B],[A|C]):- !, scan(B,C).     % previous candidate
scan( [A|B], [A|C]):- !, scan(B,C).
于 2013-01-15T15:16:25.017 に答える