Подсчет в списке прологов

Question

Я пытаюсь создать функцию пролога (я знаю, что это не функция, но я не могу вспомнить ее имя), которая дает список, а число N возвращает список с элементами, которые повторяются по крайней мере N раз.

xpto (['a', 'a', 'a', 'b', 'b', 'c'], Out, 3) должен вернуть Out = ['a']

xpto (['a', 'a', 'a', 'b', 'b', 'c'], Out, 2) должно вернуть Out = ['a', 'b']

и т. Д.

В настоящее время у меня есть:

xpto([], _, _).

xpto([H | L], O, Num) :-
    count(H, [H | L], N),
    N = Num,
    xpto(L, [H | O], Num).

xpto([H | L], O, Num) :-
    count(H, [H | L], N),
    N \= Num,
    xpto(L, O, Num).

, где в числе (A, L, N) N - количество повторений A в L, однако это не такРабота.Я уверен, что мой алгоритм работает на бумаге.

Любая помощь приветствуется:)

Answer 1

Если ваша система Prolog поддерживает clpfd , вы можете использовать следующую реализацию xpto/3.Реализация сохраняет логическую чистоту !

Давайте реализуем xpto/3 на основе list_counts/2, мета-предикатов tfilter/3 иmaplist/3 и (#=<)/3.(#=<)/3 является усовершенствованной версией ограничения (#=</2).

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

xpto(Xs,Ys,N) :-
   list_counts(Xs,Css0),
   tfilter(N+\ (_-V)^(N #=< V),Css0,Css1),
   maplist(\ (K-_)^K^true,Css1,Ys).

Давайте запустим запросы, которые вы задали в своих вопросах:

?- xpto([a,a,a,b,b,c],Out,3).
Out = [a].                        % <b>succeeds deterministically</b>

?- xpto([a,a,a,b,b,c],Out,2).
Out = [a,b].                      % <b>succeeds deterministically</b>

Поскольку код, используемый в этой реализации, monotone , мы можем задавать довольно общие запросы и по-прежнему получать логически обоснованные ответы :

?- xpto([a,a,a,b,b,c],Out,N).
Out = [],      N in 4..sup ;
Out = [a],     N = 3       ;
Out = [a,b],   N = 2       ;
Out = [a,b,c], N in inf..1 .

Теперь, как будут выглядеть ответы, если первый аргумент содержит переменные?

?- Xs = [_,_],xpto(Xs,Out,N).
Xs = [_A,_A], Out = [],       N in 3..sup             ;
Xs = [_A,_A], Out = [_A],     N in inf..2             ;
Xs = [_A,_B], Out = [],       N in 2..sup, dif(_A,_B) ;
Xs = [_A,_B], Out = [_A, _B], N in inf..1, dif(_A,_B) .

Answer 2

Рассмотрим вместо этого:

xpto(L, O, Num) :-
    % check Num is indeed a valid number
    number(Num), Num >= 0,
    % build element occurrence list EO
    elem_occ(L, EO),
    % extract all occurrences which occur at least C times
    findall(E, (member(E-Num0, EO), Num0 >= Num), O).

% computes occurrences O of elements E in a list as E-O
elem_occ([], []).
elem_occ([E|Es], [E-O|EOs]) :-
    filter([E|Es], E, ML, NL),
    length(ML, O),
    elem_occ(NL, EOs).

% filters occurrences of E from the input list and returns the remainder
filter([], _, [], []).
filter([E|Es], E, [E|Ms], Ns) :-
    !, filter(Es, E, Ms, Ns).
filter([E|Es], E0, Ms, [E|Ns]) :-
    filter(Es, E0, Ms, Ns).

Проверка с вашими примерами:

?- xpto(['a', 'a', 'a', 'b', 'b', 'c'], Out, 3).
Out = [a].

?- xpto(['a', 'a', 'a', 'b', 'b', 'c'], Out, 2).
Out = [a, b].

Это решение, вероятно, будет работать с большинством вариантов Prolog (SWI, GNU, SICStus, YAP).