1

私は数週間、自分自身にPrologを教えようとしてきました。partition/3現在、次のように機能させたい述語を使用して、いくつかの小さな整数から大きな整数を作成するすべての方法を見つけようとしています。

| ?- partition(4, [1, 2, 3], X).

X = [1, 1, 1, 1] ? ;
X = [1, 1, 2] ? ;
X = [1, 3] ? ;
X = [2, 2] ? ;
no

したがって、1、2、および3から4を作成するすべての方法を見つけます。[1、2、1]および[2、1、1]のような重複するソリューションは問題ありませんが、おそらく回避するのは難しいことではありません。これが私が今持っているものです：

partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.

partition(N, [IH|IT], [OH|OT]) :-
  N =< 0, fail;
  N > IH, M is N-IH, OH = IH,
  partition(M, [IH|IT], OT).
% if the first input IH can be subtracted from N,
% do so into M and push IH into the output list [OH|OT]

partition(N, [_|IT], Output) :-
  N =< 0, fail;
  partition(N, IT, Output). 
% after trying the first input term, try the others

Nは最終的にゼロになり、そこに到達した減算は3番目の引数にリストとして配置されるという考え方です。3番目と4番目のルールは正の整数でのみ機能し、2番目のルールは入力が不足しないように指示し、最初のルールはNがゼロに達したときにパーティションが有効であることを通知します。問題は、私が得るのは：

| ?- partition(4, [1, 2, 3], X).

no

1番目と2番目のルールは私には理にかなっています。3番目と4番目のルールは気難しいように見えますが、特に問題は見つかりません。OTMがゼロになると出力テールがインスタンス化されないかもしれないと思いましたが、最初のルールがそれを処理します。それとも、Prologがどのように機能するかについての根本的な誤解がありますか（これは私にとって頻繁に起こるようです）？

また、N =< 0, fail;部品は冗長ですか？それらは冗長に見えますが、うまくいくものを手に入れるまで確信が持てません。

編集：私はGNUPrologを使用しています。

4

1 に答える 1

2

ここで1つの問題があり、との比較がありNますIH。

partition(N, [IH|IT], [OH|OT]) :-
  N =< 0, fail;
  N > IH, [...]

する必要がありますN >= IH。

あなたの例を考えてみましょうpartition(4, [1, 2, 3], X)：

  1. 述語3と一致し、述語3はチェックしますpartition(3,[1,2,3],OT)
  2. partition(3,[1,2,3],OT)チェックする3番目の述語に一致しますpartition(2,[1,2,3],OT)。
  3. partition(2,[1,2,3],OT)チェックする3番目の述語に一致しますpartition(1,[1,2,3],OT)。
  4. partition(1,[1,2,3],OT)1> 1が失敗するため、4番目の述語に一致します。チェックpartition(1,[2,3],OT)。
  5. partition(1,[2,3],OT)4番目の述語を最後まで一致させ、リストが空の場合は失敗します。
于 2012-02-11T07:18:48.010 に答える