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

我的查詢結果，開始很好，但隨後會返回一個全球出棧錯誤：

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

如果你試圖輸入，在控制檯提示符下，這行代碼的，並要求回溯：

?- 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）是一種先進的功能...

Answer 2

在這種情況下使用庫（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). 

這裏最重要的信息是，這是定義遞歸名單本身，你真的不NE編輯一個櫃檯，更不用說有限制的一個。

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 3

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

答案的Prolog產生特定查詢中逐步顯示。也就是說，實際答案是根據需要懶散地生成的。首先，你有一些預期的答案，然後遇到一個循環。爲了確保查詢完全終止，你必須經歷所有這些查詢，打SPACE /或;每時每刻。但有一個更簡單的方法：

只需將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都是第一次出現在這裏。