如何在Prolog中獲取所有連續的子列表/子集？

Question

我想解決一個簡單的問題，但即使通過我嘗試了很多不同的方法，我找不到解決方案。我正在使用SICStus Prolog（如果有問題），並且我想要列出包含連續元素的列表的所有子列表/子集（我不知道哪個術語是正確的）。例如，如果我有列表[1，2，3，4]，調用sl/2謂詞爲sl([1, 2, 3, 4], R).，預期的結果是：

? - sl([1, 2, 3, 4], R). 
R = [] ? ; 
R = [1] ? ; 
R = [1, 2] ? ; 
R = [1, 2, 3] ? ; 
R = [1, 2, 3, 4] ? ; 
R = [2] ? ; 
R = [2, 3] ? ; 
R = [2, 3, 4] ? ; 
R = [3] ? ; 
R = [3, 4] ? ; 
R = [4] ? ; 
no 

我現在可以達到直至最好的結果是：

sl([], []). 
sl([X|Xs], [X|Ys]) :- 
    sl(Xs, Ys). 
sl([_|Xs], Ys) :- 
    sl(Xs, Ys). 

但是，這也給了我以下不需要結果除了：

R = [1,2,4] ? ; 
R = [1,3,4] ? ; 
R = [1,3] ? ; 
R = [1,4] ? ; 
R = [2,4] ? ; 

我應該如何修改我的謂詞，以便能夠得到期望的結果？

Answer 1

在Prolog中編寫謂詞時，需要考慮謂詞的含義或定義的關係。你的謂詞給出非解​​決方案的原因是你在謂詞子句中混合了含義。他們並不都是真實的意思。

你有這是指「子列表」（或「子」），但比這更謂詞sl/2，意味着按照您提供的描述子表，這是一個連續的子表（不能有任何「差距「）。現在

我們可以打破你的條款：

sl([], []). 

這是說空列表是空列表的連續子列表。這是真的，這是一個有效的事實。

sl([X|Xs], [X|Ys]) :- 
    sl(Xs, Ys). 

這就是說[X|Ys]是[X|Xs]連續子列表，如果Ys是Xs連續的子表。這種關係是不是是真的。怎樣纔是真正是真的在這裏將是：[X|Ys]是[X|Xs]連續子列表，如果Ys是一個連續的前綴子表的Xs。也就是說，Ys不僅需要成爲Xs的子列表，而且它只需要從列表的起始位置開始，而不是在此列表中的某處。這是一個線索，你需要另一個謂詞，因爲關係的含義是不同的。

你最後一句說Ys是[_|Xs]子列表，如果Ys是Xs子列表。這似乎是真的。

如果我們簡單地調整到上述更新的定義，我們可以得到：

subseq([], []). 
subseq([_|Xs], Ys) :- 
    subseq(Xs, Ys). 
subseq([X|Xs], [X|Ys]) :- 
    prefix_subseq(Xs, Ys). 

prefix_subseq(_, []). 
prefix_subseq([X|Xs], [X|Ys]) :- 
    prefix_subseq(Xs, Ys). 

我提供的prefix_subseq/2定義上面沒有任何解釋，但我認爲你自己看着辦吧。

現在，這產生了：

| ?- subseq([a,b,c,d], R). 

R = [a] ? a 

R = [a,b] 

R = [a,b,c] 

R = [a,b,c,d] 

R = [b] 

R = [b,c] 

R = [b,c,d] 

R = [c] 

R = [c,d] 

R = [d] 

R = [] 

(1 ms) yes 

定義你的子列表（或序列）的一個有趣的，緊湊的方式將使用append/2謂詞：

subseq(L, R) :- append([_, R, _], L). 

這就是說L是結果附加列表_,R和_。這個簡單實現中的小缺陷是，您將多次獲得R = []，因爲它以多種方式滿足append([_, R, _], L)規則。

的定義重新審視，您可以使用DCG來定義序列，作爲DCG是完美的處理順序：

% Empty list is a valid subsequence 
subseq([]) --> ... . 
% Subsequence is any sequence, followed by sequence we want, followed by any sequence 
subseq(S) --> ..., non_empty_seq(S), ... . 

% Definition of any sequence 
... --> [] | [_], ... . 

% non-empty sequence we want to capture 
non_empty_seq([X]) --> [X]. 
non_empty_seq([X|T]) --> [X], non_empty_seq(T). 

你還可以用phrase/2稱之爲：

| ?- phrase(subseq(S), [a,b,c,d]). 

S = [] ? ; 

S = [a] ? ; 

S = [a,b] ? ; 

S = [a,b,c] ? ; 

S = [a,b,c,d] ? ; 

S = [b] ? ; 

S = [b,c] ? ; 

S = [b,c,d] ? ; 

S = [c] ? ; 

S = [c,d] ? ; 

S = [d] ? ; 

no 

我們可以reswizzle這個定義有點和利用共同seq//1定義，使其更加緊湊：

subseq([]) --> seq(_) . 
subseq([X|Xs]) --> seq(_), [X], seq(Xs), seq(_). 

% alternatively: seq(_), seq([X|Xs]), seq(_). 

seq([]) --> []. 
seq([X|Xs]) --> [X], seq(Xs).