Prolog不结束计算？

Question

我认为这是一个相当技术性的问题，我正在尝试编写一个程序来找到整数 1,2,...,N 的所有大小为 K 的子集。

在中，我询问了我正在使用的子集函数。固定版本为：

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]):-
   N>0,
   subs(N,[A|R1],R2).

后来我写了两个函数来帮助我找到集合中的最后一个元素和除最后一个元素之外的所有元素的子集（因为[A|Rest]意味着A是第一个而Rest 是从数字 2 到最后一个，但我想要相反的 - 拥有最后一个元素和从第一个到最后一个之前的所有元素）。函数是：

lastOf(A,[A]).
lastOf(A,[B|R]):-
   lastOf(A,R).

subLast([],[X]).
subLast([A|R1],[A|R2]):-
   subLast(R1,R2).

现在我编写了一个函数来创建第一个 N 个自然数的列表：

setOf(0,[]).
setOf(N,Nums):-
   lastOf(N,Nums),
   N>0, N1 is N-1,
   subLast(NeoNums,Nums),
   setOf(N1, NeoNums).

结合以上所有我有：

choose(K,N,X):-
   setOf(N,Y),
   subs(K,X,Y).

运行它，例如 2 和 4，我得到：

?-choose(2,4,X).
X = [1, 2] ;
X = [1, 3] ;
X = [1, 4] ;
X = [2, 3] ;
X = [2, 4] ;
X = [3, 4] ;

abort
% Execution Aborted
14 ?- ERROR: Stream user_input:6:143 Syntax error: Unexpected end of clause

这些都是正确的输出，但问题是每次我按回车键输入（可能的）下一个答案后，我都会得到下一个，除了最后一个，我必须强行中止，因为程序似乎陷入了某种无限循环。

有人可以帮忙吗？

我正在使用 SWI-Prolog。

Answer 1

setOf 就是问题所在。更具体地说 - lastOf，它正在生成无限数量的以 N 结尾的可能列表。无论如何，setOf 可以更容易地以更易读的方式实现（并且正在终止）：

setOf(0, []).
setOf(N, [N|T]) :- 
    N > 0,
    N1 is N-1,
    setOf(N1, T).

如果您不关心数字的倒序，这是可以的。否则通过引入辅助谓词：

setOf(N, X) :- range(1, N, X).
% range(LowerBound, UpperBound, ResultList)
range(L, L, [L]).
range(L, U, [L|T]) :-
   L < U,
   L1 is L + 1,
   range(L1, U, T).

Answer 2

如果您使用 choose/3 的 SWI-Prolog, you can also use clpfd! Here's a clpfd 变体：

:- use_module(library(clpfd)).

choose(K,N,Zs) :-
   length(Zs,K), 
   Zs ins 1..N,
   chain(Zs,#<),
   labeling([],Zs).

就是这样！这是您在问题中给出的查询：

?- choose(2,4,Zs).
Zs = [1,2] ;
Zs = [1,3] ;
Zs = [1,4] ;
Zs = [2,3] ;
Zs = [2,4] ;
Zs = [3,4].              % the goal `choose(2,4,Zs)` terminates

Prolog不结束计算？

Prolog does not end calculation?

prolog