陷入序言中的无限循环

Question

我希望我的程序能够找到整数 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]) 卡住了。有人知道如何解决这个问题吗？

谢谢

Answer 1

你的第 4 个条款有缺陷。第二个参数（子集）的头部有一个变量 A ，它是单例的。该条款基本上是这样写的，[A|R1] 是 [B|R2] 的 N 值的子集，如果 R1 是 N 的 N 值的子集14=]，对于任何变量 A。这不是子集的正确规则，并且会导致无限循环，因为它最终不会减少到基本情况。目前尚不清楚这条规则的目的是什么。您可能只需删除它，因为前 3 个足以定义子集。

您还应该在第 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).

Answer 2

@lurker 的回答是在谓词的语义层面上。没关系。但是有一种更简单的方法来识别问题 - 只需使用以下 failure slice.

subs(0,[],_X) :- false.
subs(N,[A|R1],[A|R2]):- false, N>0, N1 is 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]) 没有终止。然而，它应该这样做。所以在剩下的可见部分有一个问题需要解决。

找到这个失败片段只有一个标准：您的查询的（普遍）未终止。没有使用有关实际预期含义的更多信息来确定此切片。

陷入序言中的无限循环

Stuck on an infinite loop in prolog

prolog

failure-slice