Wie erhalten Sie alle aufeinanderfolgenden Unterlisten/Untergruppen in Prolog?

Question

Ich möchte ein einfaches Problem lösen, aber selbst wenn ich viele verschiedene Ansätze ausprobiert habe, konnte ich keine Lösung dafür finden. Ich verwende SICStus Prolog (wenn das wichtig ist), und ich möchte alle Unterlisten/Teilmengen (ich weiß nicht, welcher Begriff das ist) von einer Liste, die Elemente in Folge enthält, erhalten. Zum Beispiel, wenn ich die Liste habe [1, 2, 3, 4], den Aufruf das sl/2 Prädikats als sl([1, 2, 3, 4], R)., das erwartete Ergebnis ist:

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

Das beste Ergebnis, das ich bis jetzt erreichen konnte, ist:

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

Aber das gibt mir auch folgende unerwünschte Ergebnisse zusätzlich:

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

Wie soll ich meine Prädikate ändern, damit ich das gewünschte Ergebnis erzielen kann?

Answer 1

Wenn Sie ein Prädikat in Prolog schreiben, müssen Sie darüber nachdenken, was das Prädikat bedeutet oder welche Beziehung es definiert. Der Grund, warum Ihr Prädikat Nicht-Lösungen ergibt, besteht darin, dass Sie Bedeutungen in Ihren Prädikatsklauseln mischen. Sie bedeuten nicht alle dasselbe.

Sie haben das Prädikat sl/2 das bedeuten sollte „sublist“ (oder „Subsequenz“), aber mehr als das, bedeutet eine Unterliste gemäß der Beschreibung, die Sie zur Verfügung gestellt, die ein zusammenhängender sublist ist (kann jeden nicht haben " Lücken "drin".

Jetzt können wir Ihre Klauseln brechen:

sl([], []). 

Dies sagt die leere Liste eine zusammenhängende Teilliste der leeren Liste ist. Dies ist wahr, so ist eine gültige Tatsache.

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

Diese besagt, dass [X|Ys] eine zusammenhängende Teilliste von [X|Xs] ist, wenn Ys eine zusammenhängende Teilliste von Xs ist. Diese Beziehung ist nicht wahr. Was wirklich wahr wäre, wäre hier: [X|Ys] eine zusammenhängende Teilliste von [X|Xs] ist, wenn Ys ein zusammenhängender Präfix sublist ist von Xs. Das heißt, nicht nur Ys muss eine Unterliste von Xs sein, aber es muss nur vom Anfang der Liste und nicht irgendwo in dieser Liste sein. Dies ist ein Hinweis darauf, dass Sie ein anderes Prädikat benötigen, da die Bedeutung der Beziehung anders ist.

Ihre letzte Klausel besagt, dass Ys eine Unterliste von [_|Xs] ist, wenn Ys eine Unterliste von Xs ist. Dies scheint wahr zu sein.

Wenn wir einfach auf die oben aktualisierten Definitionen anpassen, erhalten wir:

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

Ich bot die prefix_subseq/2 Definition oben ohne Angabe von Gründen, aber ich denke, man kann es herausfinden.

Das jetzt ergibt:

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

Eine interessante, kompakte Art und Weise Ihre sublist definieren (oder Teilfolge) würde die append/2 Prädikat werden:

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

Diese besagt, dass L ist das Ergebnis anhängende Listen _, R und _. Der kleine Fehler in dieser einfachen Implementierung ist, dass Sie mehr als einmal R = [] bekommen, da es die append([_, R, _], L) Regel in mehr als einer Weise erfüllt.

einen frischen Blick auf die Definition nehmen, können Sie eine DCG verwenden, um eine Subsequenz zu definieren, als DCG mit Sequenzen, die für den Umgang perfekt:

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

Und Sie können es mit phrase/2 nennen:

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

Wir haben diese Definition ein wenig und nutzen eine gemeinsame Definition seq//1 reswizzle können, um sie kompakter:

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

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

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