Prologで連続するサブリスト/サブセットをすべて取得する方法は？

Question

私は単純な問題を解決したいと思いますが、多くの異なるアプローチを試みても、解決策を見つけることができませんでした。私はSICStus Prologを使用しています（問題がある場合）。そして、要素を連続して含むリストのすべてのサブリスト/サブセット（どの用語が正しいかわかりません）を取得したいと思います。私がリストを持っている場合たとえば、[1、2、3、4]、sl([1, 2, 3, 4], R).としてsl/2述語を呼び出し、期待される結果は次のとおりです。私は今まで達する可能性がある

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

これはYsはXsの連続したサブリストである場合[X|Ys]は[X|Xs]の連続したサブリストであると述べています。この関係はではなく、です。本当にここに真のだろうが、次のようになります。Ysが連続プレフィックスサブリストXsのある場合[X|Ys]は[X|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および_。この単純な実装の小さな欠点は、が複数の方法でappend([_, R, _], L)のルールを満たしているため、2回以上取得されるということです。

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