我希望我的程序找到整数 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],但它从来没有给出第二个答案,因为它陷入了无限循环。我试图追踪它,似乎在找到第一个答案后它确实:
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])
卡住了。有人知道如何克服这个问题吗?谢谢
最佳答案
你的第四条有缺陷。第二个参数(子集)的头部有一个变量 A
,它是单例的。该子句基本上读取, [A|R1]
是来自 N
的 [B|R2]
值的子集,如果 R1
是来自 N
的 [B|R2]
值的子集,对于任何变量 A
。对于子集来说,这不是正确的规则,并且会导致无限循环,因为它最终不会减少到基本情况。目前尚不清楚这条规则的目的是什么。您可能可以将其删除,因为前 3 个充分定义了子集。
您还应该在第三个子句中约束 N
以避免规则匹配的重复重叠。
再加上一些变量清理使您的谓词变为:
subs(0, [], _).
subs(N, [A|R1], [A|R2]) :- N > 0, N1 is N-1, subs(N1, R1, R2).
subs(N, R1, [_|R2]) :- N > 0, subs(N, R1, R2).
关于prolog - 在序言中陷入无限循环,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/29101117/