3

クラスでは、先生が次のように与えたsubset_of/2述語について調べました。

subset_of([],[]).
subset_of([X|Xs],Zs):-subset_of(Xs,Ys),maybe_add(X,Ys,Zs).

maybe_add(_,Ys,Ys).
maybe_add(X,Ys,[X|Ys]).

subsets_of(Xs,Xss):-findall(Ys,subset_of(Xs,Ys),Xss).

それから、ある長さ K のサブセットのみを与えるように変更するように依頼されました (ただし、再帰的な定義を直接見つけることにより、長さ/2 を使用することはできません)。私の最初の試みは、subset_of 呼び出しを余分な要素を追加するものと追加しないもの (maybe_add 呼び出しの代わりに) に分割し、渡されたリストの長さを追跡して最後にチェックすることでしたが、これはまったく計画どおりに機能しませんでした。

subset_of(K, 0, [],[]).
subset_of(K, Len, [X|Xs],Zs):-
        L1 is Len - 1,
        subset_of(K, L1, Xs, Zs),
        L1 == K.
subset_of(K, Len, [X|Xs],Zs):-
        L1 is Len - 1,
        subset_of(K, L1, Xs,Ys),
        do_add(X, Ys, Zs),
        Len == K.
subsets_of(K,Xs,Xss):-
        length(Xs, Len),
        findall(Ys,subset_of(K, Len, Xs,Ys),Xss).

これを解決するための正しいコードを求めているわけではありませんが、正しい方向へのプッシュだけを求めているので、それを理解しようとし続けることができます. 宣言型言語を使用するのはこれが初めてで、かなり混乱しています。

4

2 に答える 2

1

直接的な答えが欲しくない場合は、もっと簡単にできると思います。私のソリューションには3つのルールがあります。ただし、この追加のmaybe_add数式や、それをリサンブルするものは使用しません。本当に必要な場合は、それを使用できます。引数は 5 つ、入力引数は 3 つ、出力引数は 2 つです。これにより、元のソリューションと同様に、ルールの数がsubset_of2 つだけに減ります。結局のところ、それらは非常に似ています。

また、繰り返しにも注意してください。他の回答で示唆されているsubset_of(0, _, [])ように、繰り返しにつながる方法かもしれません。ただし、それを組み込んだ正しい解決策があるかもしれませんが、ないかどうかはわかりません。

正しさの証明と考えてください。あるセットが別のセットの K 要素サブセットであることを再帰的に証明したいとします。どうやってそれについて行きますか。あなたが使用した意味を見てください。どうすればそれらを Prolog ルールに変換できますか?

于 2011-04-03T21:05:49.707 に答える
0

使用しないmaybe_addのは良い考えのようです。ただし、2 つの追加の引数は必要ありません。1 つあれば十分です。あなたの基本節は

subset_of(0, _, []).

つまり、空のセットは、要素がゼロの部分集合です。2 つの再帰句のうち、1 つはK-1要素のサブセットを検索し、もう 1 つは 要素のサブセットを検索しますK。

于 2011-04-03T20:48:06.607 に答える