3

プログラムに整数 1,2,...,N のサイズ K のすべてのサブセットを見つけてもらいたいです。

このために、次の subs(N,X,Y) は、X がセット Y のサイズ N のサブセットであることを意味します。次のように定義しました。

subs(0,[],X).
subs(N,[A|R1],[A|R2]):-N>0, N1 is N-1, subs(N1,R1,R2).
subs(N,[A|R1],[B|R2]):-subs(N,[A|R1],R2).
subs(N,[A|R1],[B|R2]):-subs(N,R1,[B|R2]).

そして、チェックとして subs(2,X,[1,2,3,4]) を実行しました。

最初の回答 [1,2] を取得しましたが、無限ループに陥ったため、2 番目の回答は得られませんでした。私はそれを追跡しようとしましたが、最初の答えを見つけた後、そうするようです:

   Redo: (8) subs(0, _G613, [3, 4]) ? creep
^  Call: (9) 0>0 ? creep
^  Fail: (9) 0>0 ? creep
   Redo: (8) subs(0, _G613, [3, 4]) ? creep
   Call: (9) subs(0, [_G618|_G619], [4]) ? creep
^  Call: (10) 0>0 ? creep
^  Fail: (10) 0>0 ? creep
   Redo: (9) subs(0, [_G618|_G619], [4]) ? creep
   Call: (10) subs(0, [_G618|_G619], []) ? creep
   Fail: (10) subs(0, [_G618|_G619], []) ? creep
   Redo: (9) subs(0, [_G618|_G619], [4]) ? creep
   Call: (10) subs(0, _G619, [4]) ? creep
   Exit: (10) subs(0, [], [4]) ? creep
   Exit: (9) subs(0, [_G618], [4]) ? creep
   Exit: (8) subs(0, [_G618], [3, 4]) ? creep
   Exit: (7) subs(1, [2, _G618], [2, 3, 4]) ?

だから私は私が立ち往生していることがわかりますsubs(0, _G619, [4])。誰かがこの問題を克服する方法を知っていますか?

ありがとう

4

2 に答える 2

2

@lurkerの答えは、述語のセマンティックレベルにあります。それはいいです。しかし、問題を特定するさらに簡単な方法があります。次の障害スライスで使用するだけです。

subs(0,[],_X) :- false .
subs(N,[A|R1],[A|R2]):- false , N>0, N1 は N-1, subs(N1,R1,R2) .
subs(N,[A|R1],[_B|R2]):- false , subs(N,[A|R1],R2) .
subs(N,[_A|R1],[B|R2]):- subs(N,R1,[B|R2]), false .

すでにこのフラグメントは で終了していませんsubs(2,X,[1,2,3,4])。ただし、そうする必要があります。したがって、残りの目に見える部分には、対処する必要がある問題があります。

この失敗スライスを見つける基準は 1 つあります。それは、(普遍的な) クエリの非終了です。このスライスを決定するために、実際に意図された意味に関するそれ以上の情報は使用されません。

于 2015-03-17T16:55:34.950 に答える