4

リスト順列にアクセスし、それを引数として他の関数に渡したいです。

これは順列コードです:

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

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

3 に答える 3

12

まず、不要な I/O を行わないように述語を再定義しましょう。

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

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

これで、「純粋な」順列関数と見なすことができるものが得られました。

?- perm([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [1, 3, 2] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
false.

したがって、値のリストを取得してツリーを生成する max_heap 関数があるとします。それについては心配させてあげるので、それが存在し、呼び出されるmax_heap/2と仮定し、さらに、この魅力的に呼び出される を表示する方法があると仮定しましょうdisplay_heap/1。順列を「取得」し、これらの関数のパラメーターとして「送信」するには、実際には数学で言っています: P が X の順列であると仮定し、それで max_heap を作成して表示します。または、P が X の順列であり、H が X から作成された最大ヒープであると仮定して、H を表示しましょう。

show_heaps(List) :- perm(List, P), max_heap(P, H), display_heap(H).

これは私の英語の文と同じことを言っています: P がリストの順列であると仮定すると、H はそのヒープ表現であり、それを表示します。技術的にdisplay_heap/1は、特定のヒープに対して true または false になる可能性がある述語です。実際には、それは常に真であり、これを実行する;と、失敗駆動ループまたはfindall/3すべてのソリューションを見つかった。

編集: 失敗によるループと について説明しましょうfindall/3。最初に、新しい述語をいくつか追加させてください。なぜなら、あなたが何をしているのか正確にはわかりませんが、私たちの目的には関係ありません。

double([X|Xs], [Y|Ys]) :- Y is X*2, double(Xs, Ys).
double([],[]).

showlist(Xs) :- print(Xs).

これdouble/2で、リストの値を 2 倍にする述語とshowlist/1、リストを標準出力に出力する述語ができました。次のように試すことができます。

?- perm([1,2,3], X), double(X, Y), showlist(Y).
[2,4,6]
X = [1, 2, 3],
Y = [2, 4, 6] ;
[4,2,6]
X = [2, 1, 3],
Y = [4, 2, 6] ;
[4,6,2]
X = [2, 3, 1],
Y = [4, 6, 2] ;
[2,6,4]
X = [1, 3, 2],
Y = [2, 6, 4] ;
[6,2,4]
X = [3, 1, 2],
Y = [6, 2, 4] ;
[6,4,2]
X = [3, 2, 1],
Y = [6, 4, 2] ;
false.

入力するとき;は、「または？」と言っています。プロローグへ。言い換えれば、あなたは「他に何を？」と言っています。あなたはプロローグに、事実上、これは私が望む答えではない、私がもっと好きな別の答えを見つけてみてくださいと言っています。このプロセスは、失敗によるループで形式化できます。

?- perm([1,2,3], X), double(X, Y), showlist(Y), fail.
[2,4,6][4,2,6][4,6,2][2,6,4][6,2,4][6,4,2]
false.

これで、各順列からの出力double/2がそこを通過し、Prolog が false を報告したことがわかります。それが、次のような意味です。

show_all_heaps(List) :- perm(List, X), double(X, Y), showlist(Y), nl, fail.
show_all_heaps(_).

それがどのように機能するかを見てください：

?- show_all_heaps([1,2,3]).
[2,4,6]
[4,2,6]
[4,6,2]
[2,6,4]
[6,2,4]
[6,4,2]
true.

もう 1 つのオプションは usingfindall/3で、次のようになります。

?- findall(Y, (perm([1,2,3], X), double(X, Y)), Ys).
Ys = [[2, 4, 6], [4, 2, 6], [4, 6, 2], [2, 6, 4], [6, 2, 4], [6, 4, 2]].

これを使用して問題を解決することは、おそらく、取り組んでいる宿題の範囲を超えています。

于 2012-02-03T20:46:37.980 に答える
3

list_permutation/2以下に基づいてsame_length/2次のselect/3ように定義できます。

:- use_module(library(lists),[same_length/2,select/3]).

list_permutation(As,Bs) :-
   same_length(As,Bs),          % redundant goal helps termination
   list_permutation_(As,Bs).

list_permutation_([],[]).
list_permutation_([A|As],Bs0) :-
    select(A,Bs0,Bs),
    list_permutation_(As,Bs).

のおかげsame_length/2で、次のクエリ 1 と 2 の両方が普遍的に終了します。

?- list_permutation([1,2,3],Ys).
  Ys = [1,2,3]
; Ys = [1,3,2]
; Ys = [2,1,3]
; Ys = [3,1,2]
; Ys = [2,3,1]
; Ys = [3,2,1]
; false.

?- list_permutation(Xs,[1,2,3]).
  Xs = [1,2,3]
; Xs = [1,3,2]
; Xs = [2,1,3]
; Xs = [2,3,1]
; Xs = [3,1,2]
; Xs = [3,2,1]
; false.

ここまでは順調ですね。しかし、重複したリスト アイテムがある場合、回答シーケンスはどのように見えるでしょうか?

?- list_permutation([1,1,1],Ys).
  Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; false.

5/6 の回答は冗長です。私たちは何ができる？!の代わりに使用するselectd/3だけです。select/3

list_permuted(As,Bs) :-
   same_length(As,Bs),
   list_permuted_(As,Bs).

list_permuted_([],[])。
list_permuted_([A|As],Bs0) :-
   selectd(A,Bs0,Bs), % selectd/3 を使用し、select/3 を使用しない
   list_permuted_(As,Bs).

前に 5 つの冗長なソリューションを提供した上記のクエリを再実行してみましょう!

?- list_permuted([1,1,1],Ys).
  Ys = [1,1,1]
; false.

?- list_permuted(Xs,[1,1,1]).
  Xs = [1,1,1]
; false.

より良い！冗長な回答はすべてなくなりました。

サンプル ケースのソリューション セットを比較してみましょう。

?- _Xs = [1,2,1,1,2,1,1,2,1],
   setof(Ys,list_permutation(_Xs,Ys),Yss),
   setof(Ys,list_permuted(_Xs,Ys),Yss),
   長さ(Yss,N)。
N = 84、Yss = [[1,1,1,1,1,1,2,2,2]、[1,1,1,1,1,2,1,2,2]、[.. .|...]|...].

わかった！サイズが少し大きい問題での経験的な実行時間の測定はどうですか? 実行時間をミリ秒単位で測定するために
使用します。call_time/2T_ms

?- call_time(\+ (list_permutation([1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 8110.

?- call_time(\+ (list_permuted(   [1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 140.

わかった！と を適切にコンパイルするif_/3と(=)/3、list_permuted/2さらに高速になります。

脚注 1: SICStus Prolog バージョン 4.3.2 (x86_64-linux-glibc2.12) を使用。
脚注 2: Prolog トップレベルからの回答は、読みやすくするために後処理されています。

于 2015-10-19T10:32:33.640 に答える