Ваша программа объединяет множество различных вопросов в один предикат. Попробуем немного их разделить. Кроме того, я предполагаю, что вы ищете максимальный подсписок из двух или более элементов, содержащих идентичные элементы.
Давайте начнем с приблизительного того, что вы хотите: Идентификация подсписков. Не беспокойтесь, что это слишком широко, мы уточним это позже. Я буду использовать 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, Sublist = [],
Postfix = [a,a,b,2,2,2,a+1,a+1,s(1,2)] ;
Prefix = [],
Sublist = "a",
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)] ;
Sublist = "aab",
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)] ;
Sublist = [2,2],
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)] ;
Sublist = [2,2],
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).
person
false
schedule
13.03.2012