list - laterales - limites y continuidad definicion

Comprueba si la frecuencia de cualquier elemento está por encima de un límite

Question

Quiero resolver un problema que es que tengo una lista de elementos de Prolog. Si cualquiera de las frecuencias del elemento es mayor que N entonces falso es el retorno. Mi expectativa es la siguiente.

?- frequency([1,2,2,2,5],3).
true.

?- frequency([1,2,2,2,2,5],3).
false.

Tengo un código para obtener una frecuencia de elemento particular. Alguna idea para el problema

count(_, [], 0) :-
   !.
count(X, [X|T], N) :-
   count(X, T, N2),
   N is N2 + 1.
count(X, [Y|T], N) :-
   X /= Y,
   count(X, T, N).

Answer 1

¿Qué hay acerca de este código ...

frequency(L,N):-getall(L,L1), max_member(A,L1),A=<N.

getall([],[]).
getall(L,N):-append([],[X1|T],L),count(X1,L,N1),getall(T,N2),append([N1],N2,N).

Answer 2

En primer lugar, puede tratar de pensar en la forma más "barata" (en términos de escritura) de atacar ese problema. Normalmente intento descubrir cómo lo haría con las herramientas de línea de comando estándar. Por ejemplo, para encontrar las ocurrencias de todas las líneas en un archivo de texto llamado foo , se escribiría (en Bash):

sort foo | uniq --count

Puede leer los manuales, pero aquí hay un ejemplo:

$ cat foo
a
b
b
b
c
d
d
a
b
d
c
$ sort foo | uniq --count
      2 a
      4 b
      2 c
      3 d

Ahora, una forma de preguntar "¿hay alguna línea que tenga un conteo por encima de 3?" es usar awk así:

sort foo | uniq --count | awk ''{ if ($1 > 3) exit(1) }''

(Estoy seguro de que también hay formas más inteligentes).

Con el archivo anterior, obtienes:

$ sort foo | uniq --count | awk ''{ if ($1 > 3) exit(1) }''
$ echo $?
1
$ sort foo | uniq --count | awk ''{ if ($1 > 4) exit(1) }''
$ echo $?
0

De acuerdo, entonces, ¿cómo te ayuda eso con Prolog? Bueno, una manera fácil de emular una tubería como esta:

foo | bar | baz # etc

es escribir en Prolog una conjunción como esta:

foo(In, X0), bar(X0, X1), baz(X1, X2) % etc

De vuelta a su problema: puede usar msort/2 (o, en cambio, se llama a un predicado de clasificación estable en la implementación que está utilizando). Entonces, necesita contar carreras del mismo elemento. En SWI-Prolog al menos tienes group_pairs_by_key/2 . Puede usarlo, por ejemplo, de la siguiente manera (junto con los otros predicados en la misma biblioteca, puede ver el código en el mismo enlace):

pairs_keys_values(Pairs, Sorted, Sorted),
group_pairs_by_key(Pairs, Grouped),
pairs_values(Grouped, Runs),
maplist(length, Runs, Counts)

En ese punto, tiene el número de ocurrencias de cada elemento en Sorted in Counts (un poco más detallado que uniq --count , uniq --count ), y solo necesita verificar si alguno de estos está por encima de su límite. Para hacer algo muy similar a la invocación awk anterior en Prolog:

maplist(=<(3), Counts)

Descargo de responsabilidad: esta es solo una forma de abordar el problema. Decidí escribirlo porque muestra que rara vez necesitas escribir mucho código si sabes qué herramientas ya tienes disponibles.

Editar

Por supuesto, no es necesario usar group_pairs_by_key/2 ; sin embargo, es muy útil saberlo, por lo que vinculé la implementación. Para este problema, sería suficiente hacer un ordenamiento estable, seguido por un predicado que simplemente cuenta el número de ocurrencias consecutivas del mismo elemento, y solo tendrá éxito si todas las ejecuciones no son más largas que el límite. La estructura básica de un predicado que hace eso es lo mismo que group_pairs_by_key/2 .

Answer 3

Use clpfd !

:- use_module(library(clpfd)).

Si construimos sobre el predicado auxiliar list_counts/2 , podemos definir la frequency/2 como esta:

frequency(Es, M) :- list_counts(Es, Xss), maplist(arg(2), Xss, Zs), maplist(#>=(M), Zs).

Consultas de muestra:

?- frequency([1,2,2,2,5], 3).
true.

?- frequency([1,2,2,2,2,5], 3).
false.

Gracias a clpfd podemos hacer consultas bastante generales , ¡y también obtener respuestas lógicamente sensatas !

?- frequency([A,B,C], 2).
       A=B ,           dif(B,C)
;                A=C , dif(B,C)
;            dif(A,C),     B=C
;  dif(A,B), dif(A,C), dif(B,C).