una resultados repetir repetidos manejo listas lista eliminar elementos ejercicios duplicar lambda prolog

lambda - resultados - manejo de listas en prolog



Empaquetar duplicados consecutivos de elementos de lista en sublistas en Prolog (6)

Lo primero es lo primero: tiene una advertencia de variable única sobre X1:

pack([H], Acc, X) :- Acc1=[H|Acc], append(X, [Acc1], X1).

Toda esta regla se reduce a esto:

pack([H], Acc, X) :- append(X, [[H|Acc]], _).

Eso seguramente no es lo que quieres, pero mirando lo que tienes aquí, no estoy seguro de lo que quieres. Para empezar, no abordaría el problema con append/3 . Su solución en realidad genera listas de valores distintos, lo que me dice que ha habido una falla de encendido bastante grave en alguna parte.

?- pack([a, a, a, a, b, c, c], X). X = [] ; X = [_G704] ; X = [_G704, _G710] ; X = [_G704, _G710, _G716] ; X = [_G704, _G710, _G716, _G722] a

Desearía poder ver el problema, porque en la traza veo que estás construyendo el resultado correctamente. Alguien con más conocimiento puede proporcionar una solución para su error tipográfico.

De todos modos, esto es lo que se me ocurrió:

pack([X|Unpacked], Packed) :- pack(Unpacked, [[X]], Packed). pack([H|T], [[H|Acc]|Rest], Packed) :- pack(T, [[H,H|Acc]|Rest], Packed). pack([X|T], [[Y|Acc]|Rest], Packed) :- X /= Y, pack(T, [[X],[Y|Acc]|Rest], Packed). pack([], RPacked, Packed) :- reverse(RPacked, Packed).

De hecho, una solución de lista de diferencias permitiría anteponer sin usar append/3 o usar reverse/2 al final, pero no tengo uno en mi bolsillo trasero.

Tengo un problema para devolver una respuesta al problema 9 de P-99: Noventa y nueve problemas de Prolog :

Empaquetar duplicados consecutivos de elementos de lista en sublistas. Si una lista contiene elementos repetidos, deben colocarse en sublistas separadas.

Consulta de muestra con resultados esperados:

?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X). X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].

Logré empacar elementos en sublistas, pero no sé cómo devolver una respuesta.

Aquí está mi código:

pack(X,Y) :- pack(X,[],Y). pack([H,H|T],Acc,X) :- pack([H|T],[H|Acc],X). pack([H,H1|T], Acc, X) :- H/=H1, Acc1=[H|Acc], append(X, [Acc1], X1), pack([H1|T],[],X1). pack([H], Acc, X) :- Acc1=[H|Acc], append(X, [Acc1], X1).

Aquí hay una consulta ejecutada en modo de rastreo:

?- trace, pack([a,a,a,a,b,c,c],X). Call: (6) pack([a, a, a, a, b, c, c], _G986) ? creep Call: (7) pack([a, a, a, a, b, c, c], [], _G986) ? creep Call: (8) pack([a, a, a, b, c, c], [a], _G986) ? creep Call: (9) pack([a, a, b, c, c], [a, a], _G986) ? creep Call: (10) pack([a, b, c, c], [a, a, a], _G986) ? creep Call: (11) a/=b ? creep Exit: (11) a/=b ? creep Call: (11) _G1100=[a, a, a, a] ? creep Exit: (11) [a, a, a, a]=[a, a, a, a] ? creep Call: (11) lists:append(_G986, [[a, a, a, a]], _G1105) ? creep Exit: (11) lists:append([], [[a, a, a, a]], [[a, a, a, a]]) ? creep Call: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep Call: (12) b/=c ? creep Exit: (12) b/=c ? creep Call: (12) _G1109=[b] ? creep Exit: (12) [b]=[b] ? creep Call: (12) lists:append([[a, a, a, a]], [[b]], _G1114) ? creep Exit: (12) lists:append([[a, a, a, a]], [[b]], [[a, a, a, a], [b]]) ? creep Call: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep Call: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep Call: (14) _G1127=[c, c] ? creep Exit: (14) [c, c]=[c, c] ? creep Call: (14) lists:append([[a, a, a, a], [b]], [[c, c]], _G1132) ? creep Exit: (14) lists:append([[a, a, a, a], [b]], [[c, c]], [[a, a, a, a], [b], [c, c]]) ? creep Exit: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep Exit: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep Exit: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep Exit: (10) pack([a, b, c, c], [a, a, a], []) ? creep Exit: (9) pack([a, a, b, c, c], [a, a], []) ? creep Exit: (8) pack([a, a, a, b, c, c], [a], []) ? creep Exit: (7) pack([a, a, a, a, b, c, c], [], []) ? creep Exit: (6) pack([a, a, a, a, b, c, c], []) ? creep X = [] .

Me imagino que debería haber una línea adicional al final de la última regla para vincular de algún modo el resultado a la entrada, pero no tengo idea de cómo hacerlo.

Algo como esto debería funcionar, creo:

%============================= % pack/2: The public interface %============================= pack( [] , [] ) . % packing an empty list yields the empty list pack( [X|Xs] , [Y|Ys] ) :- % packing a non-empty list consists of construct_run( Xs , [X] , Run , Tail ) , % - building a run of length 1 or more from the prefix of the list simplify_run( Run , Y ) , % - simplfying it for the special case of a run of length 1 pack( Tail , Ys ) % - and then recursively packing whatever is left. . % Easy! %-------------------------- % private helper predicates %-------------------------- % % construct_run/4 % construct_run( [] , Run , Run , [] ) . % the run is complete if the source list is exhausted construct_run( [X|Xs] , [R|Rs] , [R|Rs] , [X|Xs] ) :- % the run is complete if the head of the source list differs T /= R % from what''s already in the run . % construct_run( [X|Xs] , [R|Rs] , Run , Tail ) : % otherwise, T = R , % - if the head of the source list matches what''s already in the run, construct_run( Xs , [T,R|Rs] , Run , Tail ) % - we prepend it to the run and recurse down. . % % % simplify_run/2 - deal with the special case of run length 1 % simplify_run( [A] , A ) . % run length = 1 simplify_run( [A,B|C] , [A,B|C] ) . % run length > 1

Si usa SWI-Prolog, con module (library (lambda)) y foldl, puede escribir:

:- use_module(library(lambda)). pack(L, PL) :- L = [A | B], foldl(/X^Y^Z^(Y = [LY | RY], ( member(X, LY) -> Z = [[X | LY]|RY] ; Z = [[X]| [LY | RY]])), B, [[A]], RPL), reverse(RPL, PL).

El módulo lambda.pl se puede encontrar allí: http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

aquí está la modificación mínima requerida para hacer que su código funcione: agregue una variable de ''solo devolución'', para ''emerger'' el resultado del anexo de trabajo interno al nivel superior:

pack(X,Y) :- pack(X,[],_,Y). pack([H,H|T],Acc,X,R) :- pack([H|T],[H|Acc],X,R). pack([H,H1|T], Acc, X,R) :- H/=H1, Acc1=[H|Acc], append(X, [Acc1], X1), pack([H1|T],[],X1,R). pack([H], Acc, X,R) :- Acc1=[H|Acc], append(X, [Acc1], X1), R = X1.

prueba:

?- pack([a,a,a,a,b,c,c],X). X = [[a, a, a, a], [b], [c, c]] .

como has visto, hay muchos algoritmos alternativos disponibles: aquí está el mío, intenté hacerlo lo más simple posible:

pack(L, P) :- pack(L, [], P). pack([X|Xs], R, P) :- add_pack(X, R, R1), pack(Xs, R1, P). pack([], R, P) :- reverse(R, P). add_pack(X, [[X|Xs]|R], [[X,X|Xs]|R]). add_pack(X, [R|Rs], [[X],R|Rs]). add_pack(X, [], [[X]]).

su comportamiento es muy similar al ''tipo de inserción ingenuo'': toma el elemento frontal y colócalo en el lugar correcto. Para evitar agregar el elemento, utilizo un acumulador, que se revertirá al final (como la mayoría de las otras respuestas aquí).

edito , supongo, leyendo otras respuestas, que alguien más (como yo) descubrió que tu código es difícil de entender. La causa podría ser que estás mezclando argumentos de "entrada / salida". Como una elección estilística, Prologgers usualmente se adhieren a ''input first, output last''. Esto no siempre tiene sentido (después de todo, Prolog se trata de relaciones, no de funciones), pero a pesar de eso, a menudo es una técnica útil y simple de seguir.

HTH

Creo que este funcionará. Usé un "acumulador" para reunir las sublistas de miembros duplicados.

pack([], []). pack(L, Pack) :- pack(L, [], Pack). pack([X], FrontPack, [[X|FrontPack]]). pack([X,X|T], FrontPack, Pack) :- pack([X|T], [X|FrontPack], Pack). pack([X,Y|T], FrontPack, [[X|FrontPack]|Pack]) :- X /= Y, pack([Y|T], [], Pack).

Resultados:

| ?- pack([a],X). X = [[a]] ? ; no. | ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X). X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]] ? ; no | ?-

Así es como podría hacerlo de una manera lógicamente pura : use la splitlistIfAdj/3 en combinación con dif/3 , una variante reificada de prolog-dif . ¡Hagamos algunas consultas ahora mismo!

?- Xs = [a], splitlistIfAdj(dif,Xs,Pss). Xs = [ a ], Pss = [[a]]. % succeeds deterministically ?- Xs = [a,a,a,a,b,c,c], splitlistIfAdj(dif,Xs,Pss). Xs = [ a,a,a,a, b, c,c ], Pss = [[a,a,a,a],[b],[c,c]]. % succeeds deterministically ?- Xs = [a,a,a,a,b,c,c,a,a,d,e,e,e,e], splitlistIfAdj(dif,Xs,Pss). Xs = [ a,a,a,a, b, c,c, a,a, d, e,e,e,e ], Pss = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].% succeeds deterministically

A diferencia del código impuro, la implementación es monótona y se puede usar con términos no terrestres:

?- Xs = [A,B], splitlistIfAdj(dif,Xs,Pss), A=1, B=2. Xs = [1,2], A = 1, B = 2, Pss = [[1],[2]]. ?- Xs = [A,B], A=1, B=2, splitlistIfAdj(dif,Xs,Pss). % logically equivalent Xs = [1,2], A = 1, B = 2, Pss = [[1],[2]].

Tenga en cuenta que las consultas más generales como la siguiente también dan respuestas lógicamente correctas :

?- Xs = [A,B,C,D], splitlistIfAdj(dif,Xs,Pss). Xs = [D,D,D,D], Pss = [[D,D,D,D]], A=B , B=C , C=D ; Xs = [C,C,C,D], Pss = [[C,C,C],[D]], A=B , B=C , dif(C,D) ; Xs = [B,B,D,D], Pss = [[B,B],[D,D]], A=B , dif(B,C), C=D ; Xs = [B,B,C,D], Pss = [[B,B],[C],[D]], A=B , dif(B,C), dif(C,D) ; Xs = [A,D,D,D], Pss = [[A],[D,D,D]], dif(A,B), B=C , C=D ; Xs = [A,C,C,D], Pss = [[A],[C,C],[D]], dif(A,B), B=C , dif(C,D) ; Xs = [A,B,D,D], Pss = [[A],[B],[D,D]], dif(A,B), dif(B,C), C=D ; Xs = [A,B,C,D], Pss = [[A],[B],[C],[D]], dif(A,B), dif(B,C), dif(C,D).