在序言中陷入无限循环 [英] Stuck on an infinite loop in prolog

问题描述

我希望我的程序找到整数 1,2,...,N 的所有大小为 K 的子集.

I'd like my program to find me all sub-sets of size K of the integers 1,2,...,N.

为此，我写了以下 subs(N,X,Y) 表示 X 是集合 Y 的大小为 N 的子集.我定义如下:

For this, I wrote the following subs(N,X,Y) means that X is a sub-set of size N of the set Y. I defined the following:

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]).

And then as a check I ran subs(2,X,[1,2,3,4]).

我得到了第一个答案 [1,2]，但它从未给出第二个答案，因为它陷入了无限循环.我试图追踪它，似乎在找到第一个答案后:

I got the first answer [1,2], but never did it give a second answer, as it got stuck in an infinite loop. I tried to trace it, and seems that after finding the first answer it does:

   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]) 卡住了.有人知道如何克服这个问题吗?

So I see that I get stuck with subs(0, _G619, [4]). Does someone have an idea of how to overcome this problem?

谢谢

推荐答案

您的第 4 个子句有缺陷.第二个参数(子集)的头部有一个变量 A，它是单例的.该子句基本上读取，[A|R1] 是 [B|R2] 的 N 个值的子集，如果 R1 是来自 [B|R2] 的 N 个值的子集，对于任何变量 A.对于子集来说，这不是正确的规则，并且会导致无限循环，因为它最终不会减少到基本情况.目前尚不清楚这条规则的目的是什么.您可能可以将其删除，因为前 3 个充分定义了子集.

Your 4th clause has a flaw. The head of the second argument (the subset) has a variable A which is singleton. The clause basically reads, [A|R1] is a subset of N values from [B|R2] if R1 is a subset of N values from [B|R2], for any variable A. That wouldn't be a correct rule for a subset, and results in the infinite loop since it doesn't ultimately reduce to the base case. It's not clear what the purpose of this rule is. You can probably just remove it as the first 3 adequately define the subset.

您还应该在第三个子句中约束 N 以避免规则匹配的重复重叠.

You also should constrain N in the 3rd clause to avoid duplicate overlap of rule matching.

加上一点变量清理使您的谓词变成:

That plus a little variable clean-up makes your predicate into:

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).

这篇关于在序言中陷入无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！