Löschen des mittleren Elements einer Liste

Question

Ich möchte ein Prolog-Programm schreiben, um das mittlere Element aus einer ungeradzahligen Liste in eine andere Liste zu löschen.

Zum Beispiel, wenn wir geben: delete_mid([1,2,3,4,5],L)dann wird es erzeugen: L = [1,2,4,5]als Antwort.

Answer 1

Ich bin überrascht und ein bisschen traurig, dass keine der bisherigen Antworten den offensichtlichsten Ansatz verfolgt. Sicher haben Sie in der Schule davon gehört (und ich vermute, es könnte das sein, was OP erwartet).

Es ist jedoch etwas schwierig, dies zu erklären oder sofort zu tun. Hier ist zunächst ein Prädikat, um das mittlere Element zu finden :

list_mid([H|T], Mid) :-
    list_mid_1(T, T, H, Mid).

list_mid_1([], _, Mid, Mid).
list_mid_1([_,_|Fast], [S|Slow], _, Mid) :-
    list_mid_1(Fast, Slow, S, Mid).

Ich hoffe die Namen sind offensichtlich.

?- list_mid([], Mid).
false.

?- list_mid([x], Mid).
Mid = x.

?- list_mid([a,x,b], Mid).
Mid = x.

?- list_mid([a,a,x,b,b], Mid).
Mid = x.

?- list_mid([a,a,x,b], Mid).
false.

Scheint zu funktionieren. Jetzt kann ich versuchen, das Teil hinzuzufügen, in dem es das aufbewahrt, was es gerade wegwirft.

---

Ich war beschäftigt, also dauerte das eine Weile. In der Zwischenzeit ist die Antwort von Raubsauger genau das, was ich mir vorgestellt habe. Ich habe es nicht gesehen und stattdessen geschrieben:

delete_mid([H|T], L) :-
    delete_mid_1(T, T, H, L).

delete_mid_1([], Rest, _, Rest).
delete_mid_1([_,_|Fast], [H|Slow], Prev, [Prev|Back]) :-
    delete_mid_1(Fast, Slow, H, Back).

Es ist nicht so ordentlich wie die Lösung von Raubsauger, aber es scheint, dass es ansonsten dieselbe Lösung ist. Es wird für die Testfälle mit @false beendet.

---

Ich dachte, das list_middle/2Prädikat wäre genug; Ich bin wieder überrascht und ein bisschen traurig, dass nur Raubsauger es gesehen hat (oder das schon wusste).

---

Und weniger grüßt das Murmeltier

Answer 2

Und jetzt möchte ich auch mitmachen (Antwort Nr. 8 auf diese Frage).

delete_mid(Ori, Del):-
    delete_mid(Ori, Ori, Del).

delete_mid([_], [_|Slow], Slow).
delete_mid([_,_|Fast], [H|Slow], [H|Ret]):-    
    delete_mid(Fast, Slow, Ret).

?- delete_mid([1, 2, 3, 4, 5], Del).
Del = [1, 2, 4, 5] ;
false.

?- delete_mid([1, 2, 3, 4], Del).
false.

?- delete_mid(L, []).
L = [_1500] ;
false.

?- dif(A,B), delete_mid([A|_], [B|_]).
false.

---

Auf die Idee: Ich sah, wie TA_interns über das Erhalten des mittleren Elements ( ) antwortetelist_mid und dachte:
Das ist Genie. Aber warte ... das kann verbessert werden.

---

Um den Algorithmus etwas näher zu erläutern: Mit dem Prädikat kann eine Liste erstellt werden, die der (ungeradzahligen) Eingabeliste ohne mittleres Element ähnelt. Oder es kann für zwei Listen testen, ob diese Eigenschaft gilt.

Der "geniale" Teil ist, dass es nicht notwendig ist, die Länge zu berechnen oder Zähler zu haben, da tatsächlich eine Kopie der Eingabeliste als Zähler verwendet wird. Das Prinzip wird hier und hier erklärt .

In den Zeilen 1 und 2 werden zwei Verweise auf dieselbe Liste erstellt. Die Zählerliste heißt schnell, die Elementliste heißt langsam. Warum? Denn in jedem Rekursionsschritt entfernen Sie zwei Elemente aus der Schnellliste ( [_,_|Fast]), aber nur eines aus der Elementliste ( [H|Slow]). Wenn sich noch genau ein Element in der schnellen Liste befindet ( [_]), treffen Sie das mittlere Element aus der langsamen Liste. Entfernen Sie es also und legen Sie den Rest auf die Rückspur. Während Sie mit der Rekursion fortfahren, setzen Sie alle Elemente ( H), die Sie aus der langsamen Liste entfernt haben, als Kopf der Rückgabeliste ein, und die Rekursion füllt den Rest aus.

Et voilà Sie haben eine genaue Kopie der Elementliste, nur das mittlere Element fehlt.

Answer 3

Ich denke du brauchst das nth0/4Prädikat. Suchen Sie einfach den Index des mittleren Elements und entfernen Sie ihn mit nth0/4.

delete_middle(Ls, Ls1) :-
    length(Ls, L),
    divmod(L, 2, Q, 1),   % constrain remainder to be 1: fails on even list
    nth0(Q, Ls, _, Ls1).

Generative Variante: Das einzige Problem war mit divmod.

divmod1(Dividend, Divisor, Quotient, Remainder) :-
    (   var(Dividend)
    ->  Dividend is Divisor*Quotient+Remainder
    ;   divmod(Dividend, Divisor, Quotient, Remainder)
    ).

delete_middle(Ls, Ls1) :- % Reversed the clauses.
    nth0(Q, Ls, _, Ls1),
    divmod1(L, 2, Q, 1),
    length(Ls, L).

?- dif(A, B), delete_middle([A|_], [B|_]).
false.

?- delete_middle(X, []).
X = [_382] ;
false.

Answer 4

Die Lösung mit nth0/4ist effizient, aber wie wäre es, wenn wir dies deklarativ lösen?

middle_less(InList,MiddlelessList,Middle) :-
   append([Prefix,[Middle],Suffix],InList),
   length(Prefix,Len),
   length(Suffix,Len),
   append(Prefix,Suffix,MiddlelessList).

Welches ist im Grunde die Problemstellung in Prolog-Form.

Es funktioniert auch:

:- begin_tests(middleless).

test("empty list",fail) :- middle_less([],_,_).

test("1-element list",[true([MLL,M] == [[],a]),nondet]) :-
   middle_less([a],MLL,M).

test("2-element list",fail) :- 
   middle_less([a,b],_,_).

test("3-element list",[true([MLL,M] == [[a,c],b]),nondet]) :-
   middle_less([a,b,c],MLL,M).

:- end_tests(middleless).

Und so:

?- run_tests.
% PL-Unit: middleless .... done
% All 4 tests passed
true.

Aber mit einer Liste von 1001 Elementen:

?- length(L,1001),time(middle_less(L,MLL,M)).
% 757,517 inferences, 0.110 CPU in 0.111 seconds (99% CPU, 6862844 Lips)

Eines Tages verwandelt der Compiler die Spezifikation von middle_lessautomatisch in eine effiziente Lösung.

Answer 5

delete_middle([], [], _MiddleDeletedPrefix) -->
    [_Middle].
delete_middle([L | Left], [R | ReversedRight], [L | MiddleDeletedPrefix]) -->
    [L],
    delete_middle(Left, ReversedRight, MiddleDeletedPrefix),
    [R].

delete_middle(List, MiddleDeleted) :-
    phrase(delete_middle(Left, ReversedRight, MiddleDeleted), List),
    reverse(ReversedRight, Right),
    append(Left, Right, MiddleDeleted).

 

?- delete_middle([1, 2, 3, 4, 5], Xs).
Xs = [1, 2, 4, 5] ;
false.

?- delete_middle(Ls, []).
Ls = [_2542] ;
false.

?- dif(A,B), delete_middle([A|_],[B|_]).
false.

?- delete_middle(List, MiddleDeleted).
List = [_2368],
MiddleDeleted = [] ;
List = [_2368, _2392, _2374],
MiddleDeleted = [_2368, _2374] ;
List = [_2368, _2392, _2416, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2398, _2374] ;
List = [_2368, _2392, _2416, _2440, _2422, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2416, _2422, _2398, _2374] ;
List = [_2368, _2392, _2416, _2440, _2464, _2446, _2422, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2416, _2440, _2446, _2422, _2398, _2374] .  % etc.

Answer 6

Neue Version, jetzt noch deterministischer:

delete_mid(List, MiddleDeleted) :-
    List = [_ | Tail],
    gallop(Tail, MiddleDeleted, List, MiddleDeleted).

gallop([], [], [_Middle | Xs], Xs).
gallop([_,_ | Fast1], [_,_ | Fast2], [X | Xs], [X | Ys]) :-
    gallop(Fast1, Fast2, Xs, Ys).

Neu im Vergleich zu früheren Antworten ist, dass beide Listen mit doppelter Geschwindigkeit ausgeführt werden und gleichzeitig das Präfix kopiert wird. Es muss mindestens die ersten beiden Argumente flach indiziert werden, um deterministisch zu sein, aber SWI-Prolog tut dies:

?- delete_mid([1, 2, 3, 4, 5], MiddleDeleted).
MiddleDeleted = [1, 2, 4, 5].

?- delete_mid(Xs, []).
Xs = [_2008].

?- delete_mid(Xs, [a, b]).
Xs = [a, _2034, b].

?- dif(A, B), delete_mid([A | _], [B | _]).
false.

Answer 7

Aufbauend auf dem von TA_intern vorgestellten mittleren Algorithmus:

%! list_without_middle(SOURCEs,TARGETs)

list_without_middle(SOURCEs,TARGETs)
:-
list_middle(SOURCEs,_MIDDLE_,PREFIXs,SUFFIXs) ,
lists:append(PREFIXs,SUFFIXs,TARGETs)
.

%!  list_middle(LISTs,MIDDLE,PREFIXs,SUFFIXs)

list_middle([ITEM|LISTs],MIDDLE,PREFIXs,SUFFIXs)
:-
list_middle(LISTs,LISTs,ITEM,MIDDLE,PREFIXs,SUFFIXs)
.

%!  list_middle(FASTs,SLOWs,ITEM,MIDDLE,PREFIXs,SUFFIXs)

list_middle([],SLOWs,ITEM,ITEM,[],SLOWs) .

list_middle([_,_|FASTs],[ITEM|SLOWs],PREVIOUS_ITEM,MIDDLE,[PREVIOUS_ITEM|PREFIXs],SUFFIXs)
:-
list_middle(FASTs,SLOWs,ITEM,MIDDLE,PREFIXs,SUFFIXs)
.

?- list_without_middle([a,b,c],Ys).
Ys = [a, c].

?- list_without_middle([a,c],Ys).
false.

?- list_without_middle([a,b,c,d,e],Ys).
Ys = [a, b, d, e].

?- 

?- list_without_middle(Xs,Ys) .
Xs = [_924],
Ys = [] ;
Xs = [_924, _930, _936],
Ys = [_924, _936] ;
Xs = [_924, _930, _936, _948, _954],
Ys = [_924, _930, _948, _954] %.e.t.c.

?- list_middle([a,b,c],MIDDLE,PREFIXs,SUFFIXs).
MIDDLE = b,
PREFIXs = [a],
SUFFIXs = [c].

?- list_middle([a,c],MIDDLE,PREFIXs,SUFFIXs).
false.

?- list_middle([a,b,c,d,e],MIDDLE,PREFIXs,SUFFIXs).
MIDDLE = c,
PREFIXs = [a, b],
SUFFIXs = [d, e].

?- 

?- list_without_middle(Ls,[]) .
Ls = [_4364] ;
ERROR: Out of global stack
?- list_without_middle([a],Ys).
Ys = [].

?- dif(A,B) , list_without_middle([A|_],[B|_]) .
ERROR: Out of global stack
?- 

Answer 8

Diese Lösung enthält einen Zähler, um den Schwanz mit einer Liste mit der richtigen Länge zu vereinheitlichen, nachdem das mittlere Element "herausgenommen" wurde:

without_middle(Ls, Ls1):-
  without_middle(Ls, 0, Ls1).
  
without_middle([_Mid|Tail], Len, Tail):-
  length(Tail, Len).
without_middle([Item|Tail], Len, [Item|NTail]):-
  succ(Len, Len1),
  without_middle(Tail, Len1, NTail).

---

Diese geringfügige Abweichung bettet die Zählung + Länge + Vereinheitlichung der zweiten Hälfte direkter ein und führt zu besseren Leistungsergebnissen für große Listen:

without_middle(Ls, Ls1):-
  without_middle(Ls, [], Ls1).

without_middle([_Mid|Tail], Tail, Tail).
without_middle([Item|Tail], RTail, [Item|NTail]):-
   without_middle(Tail, [_|RTail], NTail).

Beispieltestfälle:

?- without_middle([a,b,c,d,e,f,g], L).
L = [a, b, c, e, f, g] ;
false.

?- without_middle([a,b,c,d,e,f], L).
false.

?- without_middle(L, []).
L = [_552] ;
false.

?- dif(A,B), without_middle([A|_], [B|_]).
false.

Answer 9

Nutzung von append/3:

del_mid([_], []).         % if input only has one element => output is []
del_mid([H|T], [H|X]) :- 
  append(M, [Litem], T),  % M = list without first and last (Litem) element
  del_mid(M, R),          % Apply on M; if M is only one item => R will be []
  append(R, [Litem], X).  % X = R + [last item] => which gets added as result's tail

Einige Beispiele:

?- del_mid([], X).
false.

?- del_mid([a], X).
X = [] ;
false.

?- del_mid([a,b], X).
false.

?- del_mid([a,b,c], X).
X = [a, c] ;
false.

?- del_mid([a,b,c,d,e,f,g], X).
X = [a, b, c, e, f, g] ;
false.

Answer 10

Weder eine einfache noch eine optimalere Antwort.

delete_middle1(Ls, Ls1) :- delete_middle1_(Ls, Ls, [], Ls1).
delete_middle1_([X | Cs], [_, _ | Ds], Acc, L) :-
    delete_middle1_(Cs, Ds, [X | Acc], L).
delete_middle1_([_ | Cs], [_], Acc, L) :-  revappend(Acc, Cs, L).

revappend([], L, L).
revappend([X | L1], L2, L3) :- revappend(L1, [X | L2], L3).

Diese Methode funktioniert gut beim Umgang mit verknüpften Listen und Zeigern. Wenn sich ein Zeiger am Ende befindet, befindet sich der andere in der Nähe der Mitte. Dann können wir einfach das Element löschen.

Answer 11

Hier ist meine Prologlösung:

delMidNumber(K,L):-
     len(K,N),
     (N mod 2 =:= 1 ->  
      N1 is N//2,
      nth0(N1,K,E1),
      del(E1,K,L); write('List has even length'),!).

len([],0).
len([H|T],N):-
    len(T,N1),
    N is N1+1.

del(E,[E|T],T).
del(E,[H|T],[H|T1]):-
    del(E,T,T1).

Das Prädikat delMidNumber akzeptiert zwei Argumente: 1-The List mit ungeraden Zahlen. 2- Die neue Liste, die erstellt wird. Das Prädikat berechnet zuerst die Länge der Liste, prüft dann, ob die Länge der Liste ungerade ist, dividiert dann die Länge durch 2. Das Ergebnis wird dann in nth0 verwendet, um uns das Element für diesen Index zu geben. Wir verwenden dann einfach das Prädikat del, um das Element mit der mittleren Zahl zu löschen. Wenn die Länge gerade ist, wird die Meldung geschrieben, dass die Länge gerade ist, und dann wird geschnitten (gestoppt).

?-delMidNumber([1,3,2,4,5],L).
L = [1, 3, 4, 5]

?-delMidNumber([1,3,4,5],L).
List has even length

Answer 12

Und hier noch ein Versuch:

delit(In, Del):-
    delit(In, In, Del, Del).

delit(Fast, [H|Slow], DelFast, Del):-
    (   Fast = [_],
        DelFast = []
    ->  Del = Slow
    ;   Fast = [_,_|Faster],
        DelFast = [_,_|DelFaster],
        Del = [H|Deler],
        delit(Faster, Slow, DelFaster, Deler)
    ).
                    
?- delit([1, 2, 3, 4, 5], Del).
Del = [1, 2, 4, 5].

?- delit([1, 2, 3, 4], Del).
false.

?- delit(L, []).
L = [_15594].

?- dif(A,B), delit([A|_], [B|_]).
false.

?- delit(L, [1,2]).
L = [1, _18882, 2].

?- delit(L, [1,2, 4, 5]).
L = [1, 2, _19916, 4, 5].

Bitte beachten Sie: Falsch deutete auf ein unerwünschtes Verhalten dieses Prädikats in früheren Versionen hin. Nachdem ich das Problem verstanden und behoben habe, indem ich einen weiteren schnellen Zähler hinzugefügt habe, habe ich jetzt eine Implementierung, die ähnlich wie Isabelles-Code funktioniert.

Auch eine andere Version mit einem Zählerprädikat, das die Anzahl der Elemente in einer ungeraden Liste Div 2 "berechnet".

count([],0).
count([_|L],s(S)):-
    count(L,S).

middel([_|Rest],0,Rest).
middel([H|List], s(s(S)), [H|Ret]):-
    middel(List, S, Ret).

middel(In, Del):-
    count(In, s(Cnt)),
    count(Del, Cnt),
    !,
    middel(In, Cnt, Del).

?- middel([1, 2, 3, 4, 5], Del).
Del = [1, 2, 4, 5].

?- middel([1, 2, 4, 5], Del).
false.

?- middel(L, []).
L = [_12056].

?- dif(A,B), middel([A|_], [B|_]).
false.

?- middel(L, [1,2]).
L = [1, _15112, 2].

?- middel(L,[1,2,3,4]).
L = [1, 2, _20964, 3, 4].