Пролог - первый список является подсписком второго списка при сохранении порядка? - PullRequest
Новая
       45

Пролог - первый список является подсписком второго списка при сохранении порядка?

2 голосов
/ 25 сентября 2019

Я хочу проверить, присутствуют ли элементы списка L1 последовательно и в том же порядке в списке L2.

Например - check ([b, c], [a, b, c, d]) должен возвращать true, в то время как check ([b, d], [a, b, c, d]) должен возвращать false

Я смотрел похожие сообщения Пролог - первый список является подсписком второго списка? , а также опробовал аналогичные решения, но всякий раз, когда я пытаюсь проверить наличие элементов, я не могу проверить, является ли порядок последовательным 

check( [], _ ).
check( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).
check( [X|XS], [_|XSS] ) :- sublist( [X|XS], XSS ).

, и если я пытаюсь проверить, является ли порядок правильным, томой код не работает. 

check( [], _ ).
check( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).

Ответы [ 3 ]

3 голосов
/ 26 сентября 2019

Альтернативное решение, использующее стандартное де-факто определение предиката append/3: 

check(SubList, List) :-
    append(Prefix, _, List),
    append(_, SubList, Prefix).

Примеры вызовов: 

| ?- check([b,d],[a,b,c,d]).

no

| ?- check([b,c],[a,b,c,d]).

true ? ;
no

| ?- check([b,c],[a,b,c,d,b,c,f]).

true ? ;
true ? ;
no

Мы также можем использовать это определение для создания подсписка-список пар: 

| ?- check(SubList, List).

SubList = [] ? ;

List = [A|_]
SubList = [A] ? ;

List = [_|_]
SubList = [] ? ;

List = [A,B|_]
SubList = [A,B] ? ;

List = [_,A|_]
SubList = [A] ? ;

List = [_,_|_]
SubList = [] ? ;

List = [A,B,C|_]
SubList = [A,B,C] ? ;

List = [_,A,B|_]
SubList = [A,B] ? ;

...

Эта проблема также дает вам возможность узнать о окончании свойствах предикатов.В качестве эксперимента измените порядок вызовов append/3, а затем проверьте, что происходит при возврате, например, для двух первых примеров вызовов.

3 голосов
/ 26 сентября 2019

Мы можем использовать append/2 [swi-doc] , чтобы написать это с одной строкой: 

subsequence(X, Y) :-
    append([_,X,_], Y).

или мы можем реализоватьsubsequence/4, который объединит две переменные Prefix и Suffix со списком до и после подпоследовательности: 

subsequence(X, Y, Prefix, Suffix) :-
    append([Prefix,X,Suffix], Y).

Здесь, таким образом, у нас есть две переменные значения, которые будут собирать префикс исуффикс до и после подпоследовательности.

2 голосов
/ 25 сентября 2019

Интересная проблема!Я удивлен тем, сколько кода потребовалось, поэтому может быть лучшее решение, чем это.

Сначала нам нужен помощник, чтобы настаивать на том, что список является префиксом другого списка.Базовый случай состоит в том, что мы исчерпали список префиксов;Индуктивный случай состоит в том, что текущие элементы совпадают, а остаток обоих списков совпадает с префиксом. 

prefix([X|Xs], [X|Ys]) :- prefix(Xs, Ys).
prefix([], _).

Теперь поиск последовательного подсписка означает поиск в списке совпадений префикса.Если текущие элементы совпадают, то наличие префикса соответствует: 

consecutive_sublist([X|Xs], [X|Ys]) :- prefix(Xs, Ys).

В противном случае мы просто отбрасываем этот элемент цели поиска и повторяем попытку в подсписке: 

consecutive_sublist(Prefix, [_|Ys]) :- consecutive_sublist(Prefix, Ys).
...