Ваша программа объединяет много разных проблем в один предикат.Попробуем немного их разделить.Кроме того, я предполагаю, что вы ищете максимальный подсписок из двух или более элементов, содержащих одинаковые элементы.
Давайте начнем с аппроксимации того, что вы хотите: Идентификация подсписков.Не беспокойтесь, что это слишком широко, мы уточним это позже.Я буду использовать DCG для этой цели.Нетерминал seq//1
описывает произвольную последовательность.
seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).
Это чрезвычайно полезный нетерминал!
?- phrase((seq(Prefix),seq(Sublist),seq(Postfix)),
[a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Prefix = Sublist, <strong>Sublist = []</strong>,
Postfix = [a,a,b,2,2,2,a+1,a+1,s(1,2)] ;
Prefix = [],
Sublist = <strong>"a"</strong>,
Postfix = [a,b,2,2,2,a+1,a+1,s(1,2)] ...
Оба ответа не ожидаются, нам нужны только подспискидлина 2 или больше, поэтому мы должны немного ограничить это определение.Скажем, требуя, чтобы Sublist
содержал как минимум два элемента.Это Sublist = [_,_|_]
.
?- Sublist = [_,_|_],
phrase((seq(Prefix),seq(Sublist),seq(Postfix)),
[a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
<strong>Sublist = "aab"</strong>,
Prefix = [],
Postfix = [2,2,2,a+1,a+1,s(1,2)] ...
Первый ответ показывает список, который мы ищем.Но второе все равно неверно: все элементы подсписка должны быть равны.Самый простой способ - использовать maplist/2
:
?- maplist(=(_),Es).
Es = [] ;
Es = [_G221] ;
Es = [_G221,_G221] ;
Es = [_G221,_G221,_G221]
Есть несколько мест, где мы могли бы заявить это требование.Я поставлю его как можно раньше:
?- Sublist = [_,_|_],
phrase(( seq(Prefix),
seq(Sublist),{maplist(=(_),Sublist)},
seq(Postfix)),
[a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
<strong>Sublist = [2,2]</strong>,
Prefix = "aab",
Postfix = [2,a+1,a+1,s(1,2)] ;
Sublist = [2,2,2],
Prefix = "aab",
Postfix = [a+1,a+1,s(1,2)] ;
<strong>Sublist = [2,2]</strong>,
Prefix = [a,a,b,2],
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
Postfix = [s(1,2)] ;
false.
Так что теперь все подсписки содержат идентичные элементы.Увы, мы получаем [2,2]
и [2,2,2]
в качестве подсписка.Нам нужен только максимальный подсписок.Итак, как мы можем описать, что такое максимальный подсписок?
Один из способов - посмотреть перед нашим подсписком: не должно быть одного и того же элемента нашего подсписка.Таким образом, либо впереди ничего (эпсилон), либо последовательность, которая заканчивается элементом, отличным от нашего.
difel(_E,[]).
difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es).
?- Sublist = [_,_|_],
phrase(( seq(Prefix),{difel(E,Prefix)},
seq(Sublist),{maplist(=(E),Sublist)},
seq(Postfix)),
[a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
E = a,
Postfix = [b,2,2,2,a+1,a+1,s(1,2)] ;
Sublist = [2,2],
Prefix = "aab",
E = 2,
Postfix = [2,a+1,a+1,s(1,2)] ;
Sublist = [2,2,2],
Prefix = "aab",
E = 2,
Postfix = [a+1,a+1,s(1,2)] ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
E = a+1,
Postfix = [s(1,2)] ;
false.
Один неверный ответ меньше.В конце все еще таится один.
?- Sublist = [_,_|_],
phrase(( seq(Prefix),{difel(E,Prefix)},
seq(Sublist),{maplist(=(E),Sublist)},
( [] | [F],{dif(E,F)},seq(_) ) ),
[a,a,b,2,2,2,a+1,a+1,s(1,2)]).
Sublist = "aa",
Prefix = [],
E = a,
F = b ;
Sublist = [2,2,2],
Prefix = "aab",
E = 2,
F = a+1 ;
Sublist = [a+1,a+1],
Prefix = [a,a,b,2,2,2],
E = a+1,
F = s(1,2) ;
false.
Это не совсем то, что вы хотели: вы просто хотели длины.Для этого добавьте length([_|Prefix],I), length(Sublist,Len)
.
Итак, вот окончательное определение:
plateau(Xs, I, Len) :-
Sublist = [_,_|_],
phrase(( seq(Prefix),{difel(E,Prefix)},
seq(Sublist),{maplist(=(E),Sublist)},
( [] | [F],{dif(E,F)},seq(_) ) ),
Xs),
length([_|Prefix],I),
length(Sublist,Len).