visit - swi prolog online

gprolog-Forma simple de determinar si una lista es una permutación de otra

Question

Intento escribir un programa de prólogo que determine si una lista es una permutación de otra. La entrada es de la forma perm(L,M) , que será verdadera si y solo si la lista L es una permutación de la lista M

Esto es para mi clase de IA, por lo que no puedo usar el ingenioso pequeño predicado de permutation que ya proporciona gprolog. Nuestro profesor señaló que el predicado member podría ser útil, pero cualquier idea que tenga que lo involucre parece requerir cosas muy difíciles y no tan declarativas (y supongo que hay una manera de resolver esto sin llegar demasiado avanzado, ya que la clase es nueva para Prolog.)

De todos modos, una forma de comprobar sería supuestamente ver que L y M son del mismo tamaño, cada elemento L está en M , y cada elemento M está en L (¡hay un uso de member !). Sin embargo, esto no sería suficiente para casos como [2,2,4] y [4,4,2] , entre otros.

Otra forma podría ser asegurar que los mismos recuentos de cada elemento estén en la lista opuesta, pero mi impresión de prólogo es que cualquier tipo de ''memoria'' variable es un asunto bastante difícil (de hecho, parece que los programas de ejemplo veo que realizar géneros, etc., ¿realmente no están manipulando datos, sino que están "reorganizando" hipotéticamente cosas y luego diciéndole sí o no ...?)

Mentalmente, uno podría simplemente ordenar ambas listas y verificar elementos uno al lado del otro, pero eso, entre toneladas de otras maneras de pensarlo, parece un poco orientado a objetos ...

¿Algún consejo? Mi mayor problema parece ser (como lo mencioné) el hecho de que hacer "operaciones" parece ser más como preguntar por ellos y esperar que las cosas se mantengan verdaderas el tiempo suficiente para llegar a donde quieres.

** ACTUALIZACIÓN: gprolog ofrece una funcionalidad de delete , pero viene con el problema declarativo relacionado que estaba esperando, dado un intento como este:

perm([LH|LT], R) :- member(LH,R), delete([LH|LT],LH,R), perm(LT,R).

En el manual, delete se define así: "delete (List1, Element, List2) elimina todas las apariciones de Element en List1 para proporcionar List2. Se requiere un término de igualdad estricto, cf. (==) / 2"

Ejecución:

{trace}
| ?- perm([1,2,3],[3,1,2]).
      1    1  Call: perm([1,2,3],[3,1,2]) ? 
      2    2  Call: member(1,[3,1,2]) ? 
      2    2  Exit: member(1,[3,1,2]) ? 
      3    2  Call: delete([1,2,3],1,[3,1,2]) ? 
      3    2  Fail: delete([1,2,3],1,[3,1,2]) ? 
      2    2  Redo: member(1,[3,1,2]) ? 
      2    2  Fail: member(1,[3,1,2]) ? 
      1    1  Fail: perm([1,2,3],[3,1,2]) ? 

(1 ms) no

** ACTUALIZACIÓN 2: ¡Creo que podría haberlo descubierto! Es un poco detallado, pero lo he probado en bastantes casos y aún no he encontrado uno malo. Si alguien ve un problema importante, indíquelo:

perm([],[]). 
perm([LH|LT],R) :- length([LH|LT],A), length(R,B), A == B, member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.
perm_recurse([],X).  %If we get here, all elements successfully matched
perm_recurse([LH|LT],R) :- member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.  

Me gusta el operador de corte ...

Answer 1

El modelo habitual a seguir es inductivo .

Si sabes cómo construir toda la permutación de elementos N-1, todas las permutaciones de N elementos se obtienen insertando el elemento en todas las posiciones disponibles.

Un ''truco de la operación'' es usar el elemento select / 3 incorporado, que, como miembro, ''mirar'' un elemento, pero lo elimina de la lista y ''devuelve'' la lista más pequeña. Esos verbos no son realmente apropiados para Prolog. Digamos que select / 3 es una relación entre un elemento, una lista que lo contiene y una lista idéntica donde falta.

Luego deja que Prolog haga toda la búsqueda ... El código resultante es realmente muy pequeño ...

Answer 2

Siempre es bueno definir un predicado más general y usarlo de una manera estrecha:

perm(X,L):- mselect(X,L,[]).

mselect([A|B],L,R):- select(A,L,M), mselect(B,M,R).
mselect([],L,L).

member no es bueno ya que deja la segunda lista sin cambios. delete tampoco sirve, ya que borra las multiplicidades.

Puede usar append though. :) También combina la selección y eliminación:

perm([A|B],L):- length(L,N), between(0,N,I),length(X,I),
  append(X,[A],Y), append(Y,Z,L),
  append(X,Z,M), perm(B,M).
perm([],[]).

Answer 3

perm(L, M) :- sort(L, X), sort(M, X).

Esto te acerca bastante y es completamente declarativo ("dos listas son permutaciones entre sí si tienen la misma representación ordenada", pero al ordenar Prolog se eliminan los duplicados). Sin embargo, tendrá éxito para casos como la perm([1,2], [2,2,2,1]) que no estoy seguro si lo desea. Sin embargo, manejará [2,2,4] y [4,4,2], ya que ambos clasifican a [2,4] . Otra solución sería algo como esto:

perm([], []).
perm([L|Ls], M) :- select(L, M, Ms), !, perm(Ls, Ms).

Esta versión no tendrá éxito para [2,2,4] y [4,4,2], pero fallará correctamente para [1,2] y [2,2,2,1]. No estoy seguro de cuál quieres, pero creo que una u otra probablemente sea correcta.

Answer 4

solo ordena ambas listas y compara el resultado