2

この質問は、重複する要素の有限セットから形成されたすべてのシーケンスを生成する (ビットを一般化する)に関する StackOverflow に関する別の質問に答えているときに出てきました。

ボリスがコメントで正しく示したように、この問題には多くの既存の解決策があります。ただし、アキュムレータ (つまり、新しく選択された要素と比較される既に選択された要素のリスト) を使用せず、dif/2代わりにステートメントを使用するソリューションに興味があります。

説明のために、次のプログラムには 4 つの要素があり、4 回の再帰呼び出しの後、div/2これまでに選択された 4 つの要素がペアごとに異なることを示すいくつかのステートメントがあります。このことから、再帰を続けて 5 番目の要素を探すのは無意味であると推測できます。これは、div/2ステートメントに与えられた要素が残っていないためです。この「知識」をプログラムにエンコードして、ループしないようにする方法はありますか?

:- use_module(library(apply)).
:- use_module(library(dif)).

sequences([]).
sequences([H|T]):-
  maplist(dif(H), T),
  between(1, 4, H),
  sequences(T).

現在のループ動作:

?- sequences(X).
X = [] ;
X = [1] ;
...
X = [4, 3, 1, 2] ;
X = [4, 3, 2, 1] ;
<LOOP>
4

2 に答える 2

2

最初の小さな問題 — 名前:sequences/1シーケンスのリスト (シーケンスが何であれ) を示唆していますが、むしろsequence/1.

あなたは非常に貧弱な Prolog システムを要求しています: あなたはより強い一貫性を要求しています。どんな価格でも、私は推測します。

私の即時反応 (使用library(clpfd)!) が機能しません。理由を見てみましょう

?- length(Xs,N),Xs ins 1..4, all_distinct(Xs).

あなたのバージョンと同じくらいループします。これは、こので最もよく確認できます。

?- length(Xs,N), false , Xs ins 1..4, all_distinct(Xs) .

だからすでにlength/2一人では間違っています。たぶん私はあなたのプログラムに繰り返し、あなたのプログラムが終了しない理由を特定しようとします:

シーケンス ([]) :- false。
シーケンス([H|T]):-
  maplist(dif(H), T), false 
  between(1, 4, H) ,
   sequence(T) .

?- シーケンス(X), false .

私たちの最愛の宣言的なポスターの子供がフラグランティにmaplist/2巻き込まれました！OK、多分私たちはそれほど厳しくするべきではありません. 結局のところ、述語を正直に終了させないことは、不謹慎で不健全または不完全なハックよりも常に望ましいことです。

理解しておく必要があるall_distinct/1のは、リストの長さを知る必要があり、すべてのドメインも存在する必要があるということです。

sequence(Xs) :-
   sequence_aux(Xs, []).

sequence_aux([], _).
sequence_aux([X|Xs], Ys) :-
   X in 1..4,
   all_distinct([X|Ys]),
   sequence_aux(Xs, [X|Ys]).

 ?- sequence(X).

これで終了します。

@mat はall_distinct([_])、削除される可能性があることに注意する場合があります。たぶんそれ以上。

余分な引数を使用するためにこの解決策が気に入らない場合は、より安全な を実装する必要がありますmaplist/2。

fmaplist(C_1, Xs) :-
    freeze(Xs, fmaplist_aux(C_1, Xs)).

fmaplist_aux(_C_1, []).
fmaplist_aux(C_1, [X|Xs]) :-
   call(C_1, X),
   freeze(Xs, fmaplist_aux(C_1, Xs)).

これで、元のプログラムを逐語的に使用できます。しかし、私はそれがあまり得意ではありません。フリーズを伴うプログラムで非終了の正確な境界を理解することは、はるかに困難です。

余談ですが、_G772-like の番号付けでは回答をトップレベル シェルに再貼り付けして正しい結果を得ることができないため、SWI で回答の置換のために正しい変数名を取得しようとする場合があります。

于 2014-12-06T23:45:12.187 に答える