Frage

Habe gerade erst den Prolog kennengelernt und versucht, ein paar einfache Übungen durchzustehen, aber bei dieser bin ich irgendwie hängengeblieben.Ich versuche, ein Programm zu schreiben, das alle Unterlisten der Eingabeliste ausgibt, wobei jede Unterliste eine Länge > 1 hat und nicht auf eine größere Unterliste erweitert werden kann.Außerdem wird die Startposition in der Liste der Unterliste ausgegeben.Eine Beispielausgabe wäre also 

| ?- plateau([a,a,b,2,2,2,a+1,a+1,s(1,2)], I, Len).
    I = 1,
    Len = 2 ? ;
    I = 4,
    Len = 3 ? ;
    I = 7,
    Len = 2 ? ;
    no

Ich bin immer noch ziemlich verwirrt von der ganzen deklarativen Sache und habe große Probleme, aus dem Imperativmodus zu wechseln.Ich denke, ich möchte, dass mein Programm so etwas tut

program([H|T],I,L):-
    T = [H1|T1] %split the tail
    ([H] = [H1] -> Count is Count+1, program(T,I,Count) 
     %if First element = second element, recurse with new values
    ; length(T,Spot), 
      %get the spot where you are in the list, so we know where sublist starts
      program(T,Spot,L) %run again, from tail, since sublist didn't have another  element?
program([],I,L). %terminate when entire list has been run through?

Soweit ich weiß, funktioniert das aus mehreren Gründen nicht.Ich setze „Zählung“ nicht zurück, also summiert es vielleicht die Werte aller Unterlisten zusammen?Gibt es eine Möglichkeit, dies zu umgehen?Mein Basisfall könnte auch nicht das sein, was ich will – ich bin mir nur nicht sicher, was er eigentlich sein soll?Ich vermisse wahrscheinlich auch andere Dinge ... jede Hilfe ist sehr dankbar!:) Danke!

War es hilfreich?

Lösung

Hier gibt es ziemlich viele komplizierte Antworten.Betrachten Sie dieses Beispiel, das weder DCGs noch viele integrierte Funktionen verwendet (vielleicht einfacher für einen Anfänger):

plateau([X|Xs], I, L) :-
    plateau(Xs, 1-1-X, I, L).

plateau([X1|Xs], I0-L0-X0, I, L) :-
    X0 == X1, !,
    NL0 is L0 + 1,
    plateau(Xs, I0-NL0-X0, I, L).

plateau(_, I-L-_, I, L) :-
    L > 1.

plateau([X|Xs], I0-L0-_, I, L) :-
    NI is I0 + L0,
    plateau(Xs, NI-1-X, I, L).

Die erste Klausel richtet den Aufruf ein, der die akkumuliert (index)-(length)-(sublist element) Tupel, als Begriff.

Die nächste Klausel erhöht die length wenn die nächste Liste element ist derselbe (beachten Sie, dass der Index nicht geändert wird).

Die dritte Klausel wird nur aufgerufen, wenn die zweite Klausel beim Testen fehlgeschlagen ist, ob die Ausführung des Unterlistenelements unterbrochen wurde (aufgrund des Schnitts). !) und gibt eine Lösung zurück, wenn die length des Laufs war > 1.

Die letzte Klausel ermöglicht es Prolog, die Suche vom letzten Durchlauf an zurückzuverfolgen und neu zu starten.

BEARBEITEN: Die Lösung von gusbro kommt dieser tatsächlich sehr nahe ...+1.

Andere Tipps

Ihr Programm vereint viele verschiedene Sachverhalte in einem Prädikat.Versuchen wir, diese etwas zu trennen.Außerdem gehe ich davon aus, dass Sie nach einer maximalen Unterliste von zwei oder mehr Elementen suchen, die identische Elemente enthalten.

Beginnen wir mit einer Annäherung an das, was Sie wollen:Unterlisten identifizieren.Machen Sie sich keine Sorgen, dass dies viel zu weit gefasst ist. Wir werden es später verfeinern.Zu diesem Zweck werde ich DCGs verwenden.Das Nicht-Terminal seq//1 beschreibt eine beliebige Sequenz.

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

Dies ist ein äußerst nützliches Nicht-Terminal!

?- phrase((seq(Prefix),seq(Sublist),seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Prefix = Sublist, Unterliste = [],
Postfix = [a,a,b,2,2,2,a+1,a+1,s(1,2)] ;
Prefix = [],
Sublist = "A",
Postfix = [a,b,2,2,2,a+1,a+1,s(1,2)] ...

Beide Antworten werden nicht erwartet, wir wollen nur Unterlisten mit einer Länge von 2 oder mehr, daher müssen wir diese Definition etwas einschränken.Sagen wir, indem wir das fordern Sublist sollte mindestens zwei Elemente enthalten.Das ist Sublist = [_,_|_].

?- Sublist = [_,_|_],
   phrase((seq(Prefix),seq(Sublist),seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Unterliste = „aab“,
Prefix = [],
Postfix = [2,2,2,a+1,a+1,s(1,2)] ...

Die erste Antwort zeigt eine Unterliste, nach der wir suchen.Aber das Zweite ist immer noch falsch:Alle Elemente der Unterliste sollten gleich sein.Der einfachste Weg ist die Verwendung maplist/2:

?- maplist(=(_),Es).
Es = [] ;
Es = [_G221] ;
Es = [_G221,_G221] ;
Es = [_G221,_G221,_G221]

Es gibt mehrere Stellen, an denen wir diese Anforderung formulieren könnten.Ich werde es so früh wie möglich formulieren:

?- Sublist = [_,_|_],
        phrase(( seq(Prefix),
                 seq(Sublist),{maplist(=(_),Sublist)},
                 seq(Postfix)),
           [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Unterliste = [2,2],
Prefix = "aab",
Postfix = [2,a+1,a+1,s(1,2)] ;
Sublist = [2,2,2],
Prefix = "aab",
Postfix = [a+1,a+1,s(1,2)] ;
Unterliste = [2,2],
Prefix = [a,a,b,2],
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
Postfix = [s(1,2)] ;
false.

Nun enthalten alle Unterlisten identische Elemente.Leider bekommen wir beides [2,2] Und [2,2,2] als Unterliste.Wir wollen nur die maximale Unterliste.Wie können wir also beschreiben, was eine maximale Unterliste ist?

Eine Möglichkeit besteht darin, vor unserer Unterliste nachzuschauen:Es darf nicht das gleiche Element unserer Unterliste geben.Es steht also entweder nichts (Epsilon) davor oder eine Sequenz, die mit einem anderen Element als unserem endet.

difel(_E,[]).
difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es).

?- Sublist = [_,_|_],
   phrase(( seq(Prefix),{difel(E,Prefix)},
            seq(Sublist),{maplist(=(E),Sublist)},
            seq(Postfix)),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
E = a,
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Sublist = [2,2],
Prefix = "aab",
E = 2,
Postfix = [2,a+1,a+1,s(1,2)] ;
Sublist = [2,2,2],
Prefix = "aab",
E = 2,
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
E = a+1,
Postfix = [s(1,2)] ;
false.

Eine falsche Antwort weniger.Am Ende lauert noch einer.

?- Sublist = [_,_|_],
   phrase(( seq(Prefix),{difel(E,Prefix)},
            seq(Sublist),{maplist(=(E),Sublist)},
            ( [] | [F],{dif(E,F)},seq(_) ) ),
      [a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
E = a,
F = b ;
Sublist = [2,2,2],
Prefix = "aab",
E = 2,
F = a+1 ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
E = a+1,
F = s(1,2) ;
false.

Das ist nicht genau das, was Sie wollten:Sie wollten einfach die Längen.Fügen Sie dazu hinzu length([_|Prefix],I), length(Sublist,Len).

Hier also die endgültige Definition:

plateau(Xs, I, Len) :-
   Sublist = [_,_|_],
   phrase(( seq(Prefix),{difel(E,Prefix)},
            seq(Sublist),{maplist(=(E),Sublist)},
            ( [] | [F],{dif(E,F)},seq(_) ) ),
      Xs),
   length([_|Prefix],I),
   length(Sublist,Len).

Ich habe versucht, Nth1 / 3-Buildin zu verwenden, hatte aber mehr Mühe, es zu arbeiten, um es zu arbeiten ... sowieso, hier eine weitere Implementierung:

generasacodicetagpre.

test:

generasacodicetagpre.

Sie könnten so etwas tun:

generasacodicetagpre.

Die erste Klausel von Plateau / 6 befasst sich mit der Kündigung des Unterlisten.Es ist entweder der Fall, dass sich der Artikel von dem von Ihnen unterscheidet, oder Sie haben das Ende der Liste erreicht.In diesem Fall gehen wir nur vor, wenn die aktuelle Länge größer ist als eins.

Die zweite Klausel befasst sich mit dem Rekursionsschritt für den Fall, dass wir das Element in der Liste noch übereinstimmen.Es fügt nur einen an den Zähler des aktuellen Unterlasters hinzu und tut der Rekursion.

Die letzte Klausel befasst sich mit dem Fall eines neuen (anderen) Elements in der Liste und setzt die Zähler einfach zurück und führt wieder auf.

Das ist unkompliziert und einfach.Wir zählen von 1;Plateau ist eine maximale Teilfolge gleicher Elemente mit einer Länge von mindestens 2;wir gehen der Liste nach.Schreiben Sie es einfach auf:

plateau(L,I,N):- plateau(L,1,I,N).                     % count from 1

plateau([A,A|B],I1,I,N):- !, more_elts(A,B,2,K,C),     % two equals, or more
    (I is I1, N is K ; plateau(C,I1+K,I,N)).
plateau([_|B],I1,I,N):- plateau(B,I1+1,I,N).           % move along the list

more_elts(A,[A|B],I,K,C):- !, more_elts(A,B,I+1,K,C).
more_elts(_,B,I,I,B).

aktualisieren: Dies setzt voraus, dass alle Elemente der Eingabeliste vorhanden sind nonvar/1.Die Tatsache, dass hier nicht instanziierte Variablen als Elemente der Eingabeliste dienen, macht den Begriff „Unterliste“ schwierig und vage.Z. B. was sind die Unterlisten von [a,X,b,b]?Kann [a,a] Und [b,b,b] beide Unterlisten der sein Dasselbe Eingabeliste? (Das erinnert mich an beobachtbare Spinwerte, Überlagerungen von Zuständen usw.irgendwie...Wenn eine Richtung der Spinbeobachtung gewählt wird, kann diese nicht mehr geändert werden ...vgl.Das ganze Gerede über „Messung“ und Quantenmechanik sokuza-kanren.scm (habe diesen Link gefunden Hier))

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top