list - palabras - prefijos en python

El prefijo común más largo(LCP) de una lista de cadenas (6)

Este es mi código hasta ahora. ¿Cómo podría optimizarlo para que imprima el prefijo, por ejemplo:

["interview", "interrupt", "integrate", "intermediate"]

debe devolver "inte"

Un poco oxidado con Prolog, no lo he hecho en mucho tiempo :)

Aquí está la variante purificada del código propuesto (y posteriormente retirado) por @CapelliC:

:- set_prolog_flag(double_quotes, chars). :- use_module(library(reif)). lists_lcp([], []). lists_lcp([Es|Ess], Ls) :- if_((maplist_t(list_first_rest_t, [Es|Ess], [X|Xs], Ess0), maplist_t(=(X), Xs)) , (Ls = [X|Ls0], lists_lcp(Ess0, Ls0)) , Ls = []). list_first_rest_t([], _, _, false). list_first_rest_t([X|Xs], X, Xs, true).

Sobre el meta-predicate maplist_t/3 hay una variante de maplist/2 que funciona con la reificación de la igualdad / desigualdad a maplist_t/5 plazo. maplist_t/5 es lo mismo con mayor aridad:

maplist_t(P_2, Xs, T) :- i_maplist_t(Xs, P_2, T). i_maplist_t([], _P_2, true). i_maplist_t([X|Xs], P_2, T) :- if_(call(P_2, X), i_maplist_t(Xs, P_2, T), T = false). maplist_t(P_4, Xs, Ys, Zs, T) :- i_maplist_t(Xs, Ys, Zs, P_4, T). i_maplist_t([], [], [], _P_4, true). i_maplist_t([X|Xs], [Y|Ys], [Z|Zs], P_4, T) :- if_(call(P_4, X, Y, Z), i_maplist_t(Xs, Ys, Zs, P_4, T), T = false).

Primero, aquí hay una consulta básica:

?- lists_lcp(["a","ab"], []). false. % fails (as expected)

Aquí están las consultas presentadas en la respuesta fina de @Fatalize .

Por último, aquí está la consulta que muestra un determinismo mejorado:

?- lists_lcp(["interview","integrate","intermediate"], Z). Z = [i,n,t,e]. % succeeds deterministically

Así es como yo implementaría esto:

:- set_prolog_flag(double_quotes, chars). longest_common_prefix([], []). longest_common_prefix([H], H). longest_common_prefix([H1,H2|T], P) :- maplist(append(P), L, [H1,H2|T]), ( one_empty_head(L) ; maplist(head, L, Hs), not_all_equal(Hs) ). one_empty_head([[]|_]). one_empty_head([[_|_]|T]) :- one_empty_head(T). head([H|_], H). not_all_equal([E|Es]) :- some_dif(Es, E). some_dif([X|Xs], E) :- if_(diffirst(X,E), true, some_dif(Xs,E)). diffirst(X, Y, T) :- ( X == Y -> T = false ; X /= Y -> T = true ; T = true, dif(X, Y) ; T = false, X = Y ).

La implementación de not_all_equal/1 es de esta respuesta por @repeat (puede encontrar mi implementación en el historial de edición).

Usamos append y maplist para dividir las cadenas en la lista en un prefijo y un sufijo, y donde el prefijo es el mismo para todas las cadenas. Para que este prefijo sea el más largo, debemos indicar que el primer carácter de al menos dos de los sufijos es diferente.

Es por eso que usamos head/2 , one_empty_head/1 y not_all_equal/1 . head/2 se utiliza para recuperar el primer carácter de una cadena; one_empty_head/1 se usa para indicar que si uno de los sufijos está vacío, automáticamente este es el prefijo más largo. not_all_equal/1 se usa para verificar o indicar que al menos dos caracteres son diferentes.

Ejemplos

?- longest_common_prefix(["interview", "integrate", "intermediate"], Z). Z = [i, n, t, e] ; false. ?- longest_common_prefix(["interview", X, "intermediate"], "inte"). X = [i, n, t, e] ; X = [i, n, t, e, _156|_158], dif(_156, r) ; false. ?- longest_common_prefix(["interview", "integrate", X], Z). X = Z, Z = [] ; X = [_246|_248], Z = [], dif(_246, i) ; X = Z, Z = [i] ; X = [i, _260|_262], Z = [i], dif(_260, n) ; X = Z, Z = [i, n] ; X = [i, n, _272|_274], Z = [i, n], dif(_272, t) ; X = Z, Z = [i, n, t] ; X = [i, n, t, _284|_286], Z = [i, n, t], dif(_284, e) ; X = Z, Z = [i, n, t, e] ; X = [i, n, t, e, _216|_224], Z = [i, n, t, e] ; false. ?- longest_common_prefix([X,Y], "abc"). X = [a, b, c], Y = [a, b, c|_60] ; X = [a, b, c, _84|_86], Y = [a, b, c] ; X = [a, b, c, _218|_220], Y = [a, b, c, _242|_244], dif(_218, _242) ; false. ?- longest_common_prefix(L, "abc"). L = [[a, b, c]] ; L = [[a, b, c], [a, b, c|_88]] ; L = [[a, b, c, _112|_114], [a, b, c]] ; L = [[a, b, c, _248|_250], [a, b, c, _278|_280]], dif(_248, _278) ; L = [[a, b, c], [a, b, c|_76], [a, b, c|_100]] ; L = [[a, b, c, _130|_132], [a, b, c], [a, b, c|_100]]; …

Hace poco tuve que implementar esto para dos listas, y este es el código que se me ocurrió. Se supone que las dos listas de entrada están suficientemente instanciadas.

longest_common_prefix([X|Xs], [X|Ys], [X|Common]) :- !, longest_common_prefix(Xs, Ys, Common). longest_common_prefix(_, _, []).

Esto se extiende fácilmente a múltiples listas:

lcs([], []). lcs([L1|Ls], Prefix) :- foldl(longest_common_prefix, Ls, L1, Prefix).

Si no te gusta usar foldl :

lcs([], []). lcs([L1|Ls], Prefix) :- lcs(Ls, L1, Prefix). lcs([], Prefix, Prefix). lcs([L1|Ls], Prefix0, Prefix) :- longest_common_prefix(L1, Prefix0, Prefix1), lcs(Ls, Prefix1, Prefix).

Primero, comencemos con algo relacionado, pero mucho más simple.

:- set_prolog_flag(double_quotes, chars). % "abc" = [a,b,c] prefix_of(Prefix, List) :- append(Prefix, _, List). commonprefix(Prefix, Lists) :- maplist(prefix_of(Prefix), Lists). ?- commonprefix(Prefix, ["interview", "integrate", "intermediate"]). Prefix = [] ; Prefix = "i" ; Prefix = "in" ; Prefix = "int" ; Prefix = "inte" ; false.

(Vea this respuesta, cómo se imprimen las listas de caracteres con comillas dobles).

Esta es la parte que es bastante fácil en Prolog. El único inconveniente es que no nos da el máximo, sino todas las soluciones posibles, incluido el máximo. Tenga en cuenta que no es necesario conocer todas las cadenas, como:

?- commonprefix(Prefix, ["interview", "integrate", Xs]). Prefix = [] ; Prefix = "i", Xs = [i|_A] ; Prefix = "in", Xs = [i, n|_A] ; Prefix = "int", Xs = [i, n, t|_A] ; Prefix = "inte", Xs = [i, n, t, e|_A] ; false.

Entonces obtenemos como respuesta una descripción parcial de la última palabra desconocida. Ahora imagina, más tarde nos damos cuenta de que Xs = "induce" . No hay problema para Prolog:

?- commonprefix(Prefix, ["interview", "integrate", Xs]), Xs = "induce". Prefix = [], Xs = "induce" ; Prefix = "i", Xs = "induce" ; Prefix = "in", Xs = "induce" ; false.

De hecho, no importa si lo afirmamos en retrospectiva o justo antes de la consulta real:

?- Xs = "induce", commonprefix(Prefix, ["interview", "integrate", Xs]). Xs = "induce", Prefix = [] ; Xs = "induce", Prefix = "i" ; Xs = "induce", Prefix = "in" ; false.

¿Podemos ahora basarnos en esta formula al máximo? Tenga en cuenta que esto efectivamente requiere alguna forma de cuantor adicional para el cual no tenemos ninguna disposición directa en Prolog. Por esta razón, tenemos que limitarnos a ciertos casos que sabemos que serán seguros. La salida más fácil sería insistir en que la lista de palabras no contenga ninguna variable. iwhen/2 para este propósito.

maxprefix(Prefix, Lists) :- iwhen(ground(Lists), maxprefix_g(Prefix, Lists)). maxprefix_g(Prefix, Lists_g) :- setof(N-IPrefix, ( commonprefix(IPrefix, Lists_g), length(IPrefix, N ) ), Ns), append(_,[N-Prefix], Ns). % the longest one

La desventaja de este enfoque es que obtenemos errores de instanciación en caso de que no se conozca la lista de palabras.

Tenga en cuenta que hicimos algunas suposiciones (que espero que realmente se cumplan). En particular, asumimos que hay exactamente un máximo. En este caso, esto es válido, pero en general podría ser que haya varios valores independientes para el Prefix . También, asumimos que IPrefix siempre será molido. Podríamos comprobar eso también, solo para estar seguros. Alternativamente:

maxprefix_g(Prefix, Lists_g) :- setof(N, IPrefix^ ( commonprefix(IPrefix, Lists_g), length(IPrefix, N ) ), Ns), append(_,[N], Ns), length(Prefix, N), commonprefix(Prefix, Lists_g).

Aquí, el prefijo no tiene que ser un solo prefijo (que está en nuestra situación).

La mejor, sin embargo, sería una versión más pura que no necesite recurrir a errores de instanciación.

Una versión simple:

:- set_prolog_flag(double_quotes, chars). pref([],_,[]). pref(_,[],[]). pref([H|T1],[H|T2],[H|Tr]):- pref(T1,T2,Tr). pref([H|_],[H|_],[]). pref([H1|_],[H2|_],[]):- dif(H1,H2). lcf([],[]). lcf([W],R):- pref(W,W,R). lcf([W1,W2|L],R):- pref(W1,W2,R), lcf([W2|L],R).

Ejemplos:

pref("interview","integrate",R). R = [i, n, t, e] ; R = [i, n, t] ; R = [i, n] ; R = [i] ; R = [] ; False. lcf(["interview", "interrupt", "integrate", "intermediate"],R). R = [i, n, t, e] lcf(["interview", "interrupt", X, "intermediate"],R). R = X, X = [i, n, t, e, r]

Esta respuesta anterior presentó una implementación basada en if_/3 .

:- use_module(library(reif)).

Aquí viene una versión algo diferente de esto:

lists_lcp([], []). lists_lcp([Es|Ess], Xs) :- foldl(list_list_lcp, Ess, Es, Xs). % foldl/4 list_list_lcp([], _, []). list_list_lcp([X|Xs], Ys0, Zs0) :- if_(list_first_rest_t(Ys0, Y, Ys) % if_/3 , ( Zs0 = [X|Zs], list_list_lcp(Xs, Ys, Zs) ) , Zs0 = [] ). list_first_rest_t([], _, _, false). list_first_rest_t([X|Xs], Y, Xs, T) :- =(X, Y, T). % =/3

Casi todas las consultas en mi respuesta anterior dan las mismas respuestas, así que no las muestro aquí.

lists_lcp([X,Y], "abc") , sin embargo, ya no termina universalmente con el nuevo código.