Supprimer l'élément du milieu d'une liste

Je pense que vous avez besoin du prédicat nth0/4 . nth0/4 simplement l'index de l'élément du milieu, puis supprimez-le en utilisant nth0/4 .

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

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

Variante générative: Le seul problème était avec 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).

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

La solution avec nth0/4 est efficace, mais que diriez-vous de résoudre cela de manière déclarative?

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

Ce qui est essentiellement l'énoncé du problème sous forme Prolog.

Cela fonctionne également:

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

Et donc:

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

Mais avec une liste de 1001 éléments:

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

Un jour, le compilateur transforme middle_less la spécification de middle_less en une solution efficace.

Je suis surpris et un peu attristé qu'aucune des réponses à ce jour n'adopte l'approche la plus évidente; vous en avez sûrement entendu parler à l'école (et je soupçonne que c'est peut-être ce que l'on attend d'OP).

C'est cependant un peu difficile à expliquer ou à faire à la fois, alors voici d'abord un prédicat pour trouver l'élément du milieu:

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

J'espère que les noms sont évidents.

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

Semble fonctionner. Maintenant, je peux essayer d'ajouter la partie où elle garde ce qu'elle jette pour le moment.

J'étais occupé alors cela a pris un certain temps. En attendant, la réponse de Raubsauger est exactement ce que j'avais en tête. Je ne l'ai pas vu et j'ai plutôt écrit ceci:

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

Ce n'est pas aussi net que la solution de Raubsauger mais il semble que ce soit autrement la même solution. Il se termine pour les cas de test par @false.

Je pensais que le prédicat list_middle/2 était suffisant; Je suis à nouveau surpris et un peu attristé que seul Raubsauger l'ait vu (ou le savait déjà).

Und täglich grüßt das Murmeltier

Pas une réponse simple ni une réponse plus optimale.

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

Cette méthode fonctionne bien lorsqu'il s'agit de listes chaînées et de pointeurs. Lorsqu'un pointeur est à la fin, l'autre sera près du milieu. Ensuite, nous pouvons simplement supprimer l'élément.

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

En s'appuyant sur l'algorithme de recherche du milieu présenté par TA_intern:

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

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

Cette solution garde un compteur pour unifier la queue avec une liste de longueur appropriée après avoir "retiré" l'élément du milieu:

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

Cette légère variation intègre plus directement le comptage + la longueur + l'unification de la seconde moitié, ce qui donne de meilleurs résultats de performance pour les grandes listes:

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

Exemples de cas de test:

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

Et maintenant, je veux me joindre aussi (réponse n ° 8 à cette question).

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.

À l'idée: j'ai vu la réponse de TA_interns sur l'obtention de l'élément du milieu ( list_mid ) et list_mid pensé:
C'est du génie. Mais attendez ... cela peut être amélioré.

Pour expliquer un peu plus l'algorithme: le prédicat peut être utilisé pour générer une liste qui est similaire à la liste d'entrée (impaire) sans élément central. Ou il peut tester deux listes si cette propriété est vérifiée.

La partie "génie" est qu'il n'est pas nécessaire de calculer la longueur ou d'avoir des compteurs car il utilise en fait une copie de la liste d'entrée comme compteur. Le principe est expliqué ici et ici .

Les lignes 1 et 2 créent deux références à la même liste. La liste des compteurs est appelée rapide, la liste des éléments est appelée lente. Pourquoi? Parce qu'à chaque étape de récursion, vous supprimez deux éléments de la liste rapide ( [_,_|Fast] ) mais un seul de la liste d'éléments ( [H|Slow] ). Quand il y a exactement un élément dans la liste rapide à gauche ( [_] ), vous frappez l'élément central de la liste lente. Alors enlevez-le et mettez le reste sur la piste de retour. En continuant avec la récursion, mettez tous les éléments ( H ) que vous avez supprimés de la liste lente en tête de la liste de retour, et la récursion remplit le reste.

Et voilà, vous avez une copie exacte de la liste des éléments, il manque seulement l'élément du milieu.

Essaye ça:

import math

def delete_mid(array):
    array.pop(math.floor(len(array) / 2))
    return array

Utilisation de append/3 :

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

Quelques exemples:

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

Voici ma solution prologue:

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

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

Le prédicat delMidNumber prend deux arguments 1-La liste avec des nombres impairs. 2- La nouvelle liste qui sera formée. Le prédicat calcule d'abord la longueur de la liste, il vérifie ensuite si la longueur de la liste est impaire puis il divise la longueur par 2. Le résultat est ensuite utilisé dans nth0 pour nous donner l'élément sur cet index. Nous utilisons ensuite simplement le prédicat del pour supprimer cet élément de numéro intermédiaire. Si la longueur est paire, il écrit le message que la longueur est paire puis coupe (s'arrête).

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

Nouvelle version, désormais encore plus déterministe:

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

Ce qui est nouveau par rapport aux réponses précédentes, c'est que cela parcourt les deux listes à double vitesse, tout en copiant le préfixe en même temps. Il a besoin d'une indexation superficielle sur au moins les deux premiers arguments pour être déterministe, mais SWI-Prolog le fait:

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

Et voici un autre essai:

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

L'idée est la même que dans mon autre réponse, mais cette fois, il utilise un if-then-else pour éviter le retour en arrière.

Aussi une version différente avec un prédicat compteur qui "calcule" le nombre d'éléments dans une liste impaire Div 2.

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

delit(Fast,[H|Slow],Out):-
    (   Fast = [_],
        Out = Slow
    ->  true
    ;   Fast = [_,_|Faster],
        delit(Faster, Slow, Outer),
        Out = [H|Outer]
    ).


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

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

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

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

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