Prolog 出栈错误

Question

我正在研究 99 Prolog Problems 中的第 26 题：

P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list

Example:
?- combination(3,[a,b,c,d,e,f],L).

L = [a,b,c] ;

L = [a,b,d] ;

L = [a,b,e] ;

所以我的程序是：

:- use_module(library(clpfd)).

combination(0, _, []).
combination(Tot, List, [H|T]) :- 
    length(List, Length), Tot in 1..Length,
    append(Prefix, [H], Stem), 
    append(Stem, Suffix, List), 
    append(Prefix, Suffix, SubList),
    SubTot #= Tot-1,
    combination(SubTot, SubList, T).

我的查询结果一开始很好，但随后 returns 出现全局堆栈错误：

?- combination(3,[a,b,c,d,e,f],L).
L = [a, b, c] ;
L = [a, b, d] ;
L = [a, b, e] ;
L = [a, b, f] ;
Out of global stack

我不明白为什么一开始它可以工作，但后来一直挂起，直到出现全局堆栈错误。发生在终端的 SWISH 和 swi-prolog 上。

Answer 1

在这种情况下使用库(clpfd) 非常可疑。 length(List, Length)之后，Length肯定是绑定了一个非负整数，为什么还要绑定呢？而且你的 Tot in 1..Length 也很奇怪，因为你在递归的每一步都不断地创建一个新的约束变量，和你试图将它与 0 统一起来。我不是确定我理解你的整体逻辑:-(

如果我理解练习的要求，我会建议采用以下更简单的方法。首先，确保您的 K 不大于元素总数。然后，一次只选择一个元素，直到你有足够的。它可能是这样的：

k_comb(K, L, C) :-
    length(L, N),
    length(C, K),
    K =< N,
    k_comb_1(C, L).

k_comb_1([], _).
k_comb_1([X|Xs], L) :-
    select(X, L, L0),
    k_comb_1(Xs, L0).

这里的重要信息是定义递归的是列表本身，你真的不需要计数器，更不用说有约束的计数器了。

select/3 是教科书中的谓词，我想你也应该在标准库中找到它；无论如何，参见 here 实现。

这会执行以下操作：

?- k_comb(2, [a,b,c], C).
C = [a, b] ;
C = [a, c] ;
C = [b, a] ;
C = [b, c] ;
C = [c, a] ;
C = [c, b] ;
false.

以你的例子为例：

?- k_comb(3, [a,b,c,d,e,f], C).
C = [a, b, c] ;
C = [a, b, d] ;
C = [a, b, e] ;
C = [a, b, f] ;
C = [a, c, b] ;
C = [a, c, d] ;
C = [a, c, e] ;
C = [a, c, f] ;
C = [a, d, b] ;
C = [a, d, c] ;
C = [a, d, e] ;
C = [a, d, f] ;
C = [a, e, b] ;
C = [a, e, c] . % and so on

请注意，这不会检查第二个参数中列表的元素是否确实是唯一的；它只是从不同的位置获取元素。

此解决方案仍然存在终止问题，但我不知道这是否与您相关。

Answer 2

如果您尝试在控制台提示符下输入这行代码，并请求回溯：

?- append(Prefix, [H], Stem).
Prefix = [],
Stem = [H] ;
Prefix = [_6442],
Stem = [_6442, H] ;
Prefix = [_6442, _6454],
Stem = [_6442, _6454, H] ;
...

也许您对（主要）问题有所了解。所有 3 个变量都是免费的，然后 Prolog 继续生成越来越长的回溯列表。正如鲍里斯已经建议的那样，你应该让你的程序更简单......例如

combination(0, _, []).
combination(Tot, List, [H|T]) :- 
    Tot #> 0,
    select(H, List, SubList),
    SubTot #= Tot-1,
    combination(SubTot, SubList, T).

产生

?- aggregate(count,L^combination(3,[a,b,c,d,e],L),N).
N = 60.

恕我直言，在您迈出进入 Prolog 的第一步时，库 (clpfd) 不会让您的生活变得更简单。使用可用的基本结构对普通 Prolog 进行建模和调试已经很困难，而 CLP(FD) 是一项高级功能...

Answer 3

I can't understand why it works at first, but then hangs until it gives Out of global stack error.

Prolog 为特定查询生成的答案是递增显示的。也就是说，实际答案是按需延迟生成的。首先，有一些你期望的答案，然后遇到了循环。为确保查询完全终止，您必须遍历所有查询，点击 SPACE/or ；每时每刻。但是有一个更简单的方法：

只需在查询末尾添加 false。现在，所有答案都被隐藏了：

?- combination(3,[a,b,c,d,e,f],L), false.
ERROR: Out of global stack

通过在程序中添加更多 false 目标，您可以定位真正的罪魁祸首。请参阅下面我所有的尝试：我从第一次尝试开始，然后进一步添加 false 直到找到终止片段 (failure-slice).

combination(0, _, []) :- false.                % 1st
combination(Tot, List, [H|T]) :-
    length(List, Length), Tot in 1..Length,    % 4th terminating
    append(Prefix, [H], Stem), false,          % 3rd loops
    append(Stem, Suffix, List), false,         % 2nd loops
    append(Prefix, Suffix, SubList),
    SubTot #= Tot-1, false,                    % 1st loops
    combination(SubTot, SubList, T).

要解决未终止的问题，您必须修改剩余可见部分的某些内容。显然，Prefix 和 Stem 都是第一次出现在这里。

Prolog 出栈错误

Prolog Out of stack error

permutation

prolog

combinatorics

backtracking

failure-slice