4

我正在处理99 Prolog Problems中的第 26 题：

P26 (**) 生成从列表的 N 个元素中选择的 K 个不同对象的组合

例子：

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

我的查询结果开始正常，但随后返回全局堆栈错误：

?- 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 上。

4

3 回答 3

2

我不明白为什么它一开始可以工作，但后来挂起，直到它给出全局堆栈错误。

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

只需false在查询末尾添加即可。现在，所有的答案都被压制了：

?- 组合（3，[a，b，c，d，e，f]，L），假。
错误：超出全局堆栈

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

组合（0，_，[]）：-假。% 第一
组合（Tot，列表，[H|T]）：-
    length(List, Length), Tot in 1..Length, % 4th 终止
    append(Prefix, [H], Stem), false , % 3rd 循环
    append(Stem, Suffix, List) , false , % 2nd 循环
    append(Prefix, Suffix, SubList) ,
     SubTot #= Tot-1 , false , % 1st循环
    组合（SubTot，SubList，T）。

要消除不终止的问题，您必须修改剩余可见部分中的某些内容。显然，两者都是Prefix第Stem一次出现在这里。

于 2017-03-11T23:15:33.577 回答
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.

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

于 2017-03-11T07:59:31.200 回答
0

在这种情况下使用 library(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是教科书谓词，我想您也应该在标准库中找到它；无论如何，请参阅此处以获取实现。

这将执行以下操作：

?- 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

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

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

于 2017-03-11T07:40:25.903 回答