Самая длинная последовательность в прологе

Мне нужно удалить самую длинную последовательность простых чисел из списка в Прологе. Я новичок в Прологе и не могу найти способ добраться до самой длинной последовательности... Вот что я сделал до сих пор:

divisible(X,Y):-
  0 is X mod Y.
divisible(X,Y):-
  X > Y + 1,
  divisible(X,Y+1).

is_prime(2).
is_prime(3).
is_prime(P):-
  integer(P),
  P>3,
  P mod 2 =\= 0,
  not(divisible(P,3)).

Этот удаляет простые числа из списка.

removeP([],[]).
removeP([H],[H]):-
  not(is_prime(H)).
removeP([H|T],[H|L]):-
  not(is_prime(H)),
  removeP(T,L).
removeP([H|T],L):-
  is_prime(H),
  removeP(T,L).

И вот я пытался найти самую длинную последовательность, но я понятия не имею, что делать дальше

longest([],[]).
longest([H],[H]):-
  is_prime(H).
longest([H],[]):-
  not(in_prime(H)).
longest([H|T],L):-
  ....

person LauraW    schedule 04.11.2015    source источник
comment
Предоставьте несколько примеров запросов вместе с ожидаемыми ответами.   -  person repeat    schedule 04.11.2015
comment
Я предполагаю, что вас интересуют не подпоследовательности, а подсписки. сравните en.m.wikipedia.org/wiki/Subsequence и en.m.wikipedia.org/wiki/Подстрока .   -  person repeat    schedule 04.11.2015
comment
Например, если у меня есть список [1, 3, 5, 4, 2, 5, 7, 8], результирующий список будет [1, 3, 5, 4, 8] как [2,5,7] является самым длинным.   -  person LauraW    schedule 04.11.2015
comment
Ok. Что делать, если список [1,3,5,4, 2,5,7, 8, 2,5,7, 9]? Следует ли удалить оба вхождения [2,5,7]?   -  person repeat    schedule 04.11.2015
comment
Что делать, если список [1,3,5,4, 2,5,7, 8, 2,3,5, 9]? Следует ли удалить все самые длинные подсписки (состоящие только из простых чисел)? Или нам лучше получить два ответа (один с удаленным [2,5,7], другой с удаленным [2,3,5])?   -  person repeat    schedule 04.11.2015
comment
Я предполагаю, что это должно быть удалено все из них .. если размер тот же.   -  person LauraW    schedule 04.11.2015


Ответы (1)


библиотеки, особенно aggregate, помогают использовать недетерминизм:

remove_longest(Pred, L, R) :-
    aggregate(max(C,Xc/Yc), P^(append([Xc,P,Yc],L), maplist(Pred,P), length(P,C)), max(C,X/Y)),
    append(X, Y, R).

предикат (is_prime для вашего случая) остается общим. В этом примере запуска я использую только идентификатор атома «a»:

?- remove_longest(=(a), [1,2,3,a,a,4,5,a], R).
R = [1, 2, 3, 4, 5, a].
person CapelliC    schedule 04.11.2015
comment
Интересно, можно ли это сделать неквадратичным? - person Mostowski Collapse; 30.07.2019