Как проверить, является ли список непустым подсписком другого списка в Prolog

Я пытаюсь создать included_list(X,Y) термин, который проверяет, является ли X непустым подсписком Y.

Я уже использую это для проверки наличия элементов в списке Y

check_x(X,[X|Tail]).
check_x(X,[Head|Tail]):- check_x(X,Tail).

И добавляемый термин

append([], L, L).
append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).

создать список, чтобы программа завершилась на

included_list([HeadX|TailX],[HeadX|TailX]).

но у меня возникают проблемы с обработкой нового пустого списка, который я пытаюсь создать с помощью «добавления» (я хочу создать пустой список для добавления элементов, существование которых подтверждено в обоих списках).

Я нашел это

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

но оказывается истинным в подсписке ([], [1,2,3,4)


prolog sublist
person Crownless    schedule 26.01.2015    source источник
comment
если есть подсписок, предусматривающий заказ? или порядок не имеет значения. ?   -  person levi    schedule 26.01.2015
comment
не могли бы вы уточнить, но у меня проблемы с обработкой нового пустого списка, который я пытаюсь создать с помощью добавления? обработка чего? как создать пустой список и для чего его использовать?   -  person LeleDumbo    schedule 26.01.2015
comment
Возможно, вы захотите увидеть: stackoverflow.com/questions/7051400/   -  person user2520215    schedule 26.01.2015
comment
@ user2520215 это работает для пустых подсписок.   -  person Crownless    schedule 26.01.2015
comment
@LeleDumbo Я хочу создать пустой список для добавления элементов, существование которых подтверждено в обоих списках.   -  person Crownless    schedule 26.01.2015

Ответы (5)


arrow_upward
5
arrow_downward

Поскольку вы ищете несмежный подсписок или упорядоченное подмножество и не хотите включать пустой список, тогда:

sub_list([X], [X|_]).
sub_list([X], [Y|T]) :-
    X \== Y,
    sub_list([X], T).
sub_list([X,Y|T1], [X|T2]) :-
    sub_list([Y|T1], T2).
sub_list([X,Y|T1], [Z|T2]) :-
    X \== Z,
    sub_list([X,Y|T1], T2).

Некоторые результаты:

| ?- sub_list([1,4], [1,2,3,4]).

true ? a

no
| ?- sub_list(X, [1,2,3]).

X = [1] ? a

X = [2]

X = [3]

X = [1,2]

X = [1,3]

X = [1,2,3]

X = [2,3]

(2 ms) no
| ?- sub_list([1,X], [1,2,3,4]).

X = 2 ? a

X = 3

X = 4

(2 ms) no

Обратите внимание, что он не просто сообщает вам, является ли один список подсписком другого, но и отвечает на более общие вопросы, например, Какие подсписки L? Когда сокращения используются в предикатах, в этом случае он может удалить возможные действительные решения. Таким образом, это решение позволяет избежать использования разреза по этой причине.

Объяснение:

Идея состоит в том, чтобы сгенерировать набор правил, которые определяют, что такое подсписок, и попытаться сделать это, не будучи процедурными или императивными. Вышеупомянутые пункты можно интерпретировать как:

  1. [X] - это подсписок списка [X|_]
  2. [X] - это подсписок списка [Y|T], если X и Y различны, а [X] - подсписок списка T. Условие X и Y различное предотвращает перекрытие этого правила с правилом №1 и значительно сокращает количество выводов, необходимых для выполнения запроса, за счет исключения ненужных рекурсий.
  3. [X,Y|T1] - это подсписок [X|T2], если [Y|T1] - подсписок T2. Форма [X,Y|T1] гарантирует, что список содержит как минимум два элемента, чтобы не перекрывать правило № 1 (что может привести к тому, что любое решение будет повторяться более одного раза).
  4. [X,Y|T1] - это подсписок [Z|T2], если X и Z разные, а [X,Y|T1] - подсписок T2. Форма [X,Y|T1] гарантирует, что список содержит по крайней мере два элемента, чтобы не перекрываться с правилом № 2, а условие X и Z разное предотвращает перекрытие этого правила с правилом № 3 (что может привести к повторению любого отдельного решения). чем один раз) и значительно сокращает количество выводов, необходимых для выполнения запроса, избегая ненужных рекурсий.
person lurker    schedule 26.01.2015
comment
Не могли бы вы объяснить, как работает ваш код? Хотя вроде работает нормально :) - person Crownless; 26.01.2015
comment
Спасибо за ваше объяснение. Я новичок в прологе, и мне сложно понять процессы рекурсии. Вы что-нибудь редактировали в коде? - person Crownless; 26.01.2015
comment
@Crownless - К вашему сведению, я думаю, что ответ user2520215 теперь работает так же хорошо и является более кратким. - person lurker; 26.01.2015
comment
Верно, но мне очень нравится ваше объяснение. - person Crownless; 26.01.2015
comment
Могут ли последние 2 правила быть такими: sub_list([X|T1], [X|T2]) :- sub_list(T1, T2). sub_list([X|T1], [Z|T2]) :- X \== Z, sub_list([X|T1], T2). - person Crownless; 28.01.2015
comment
@Crownless см. Мои объяснения № 3 и № 4 относительно того, почему используется форма [X,Y|T1]. Он избегает дублирования с другими правилами, что может привести к повторным решениям. Итак, используя предложенные вами изменения, запрос sub_list([1], [1,2]) будет соответствовать как правилу №1, так и правилу №3. И запрос sub_list([1,4], [1,2,3,4]). выполняется 4 раза, а не один раз, даже если [1,4] на самом деле является только подсписком один раз в [1,2,3,4]. Другими словами, предикат не дает правильных результатов. - person lurker; 28.01.2015
comment
Итак, ваш код не даст повторяющихся (или более) ответов в любой конкретной ситуации, верно? - person Crownless; 28.01.2015

arrow_upward
1
arrow_downward

Вот что вы делаете:

mysublist(L,L1):- sublist(L,L1), notnull(L).

notnull(X):-X\=[].

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

Взяв ссылку из этого: Пролог - первый список является подсписком второго списка? Я просто добавил условие, чтобы заранее проверить, пусто ли оно.

Надеюсь это поможет.

person user2520215    schedule 26.01.2015
comment
Кажется, это ответ на мою проблему :) - person Crownless; 26.01.2015
comment
Если бы вы могли объяснить мне этот код и то, как он работает, я был бы очень благодарен. :) - person Crownless; 26.01.2015
comment
mysublist(S, [1,2,3]) возвращает false, значит, [1,2,3] не имеет подсписок, S. - person lurker; 26.01.2015
comment
@ user2520215 Не могли бы вы добавить пояснение к последним трем правилам подписок, как это сделал lurker? - person Crownless; 26.01.2015
comment
Скорее: mysublist(L,L1) :- L = [_|_], sublist(L,L1). и подсписок имен очень неудачный, используйте вместо этого подпоследовательность. - person false; 28.01.2015

arrow_upward
0
arrow_downward

Если порядок имеет значение. Пример [1,2,3] - это подсписок [1,2,3,4], а [1,3,2] - нет.

Вы можете сделать что-то подобное.

sublist([],L).
sublist([X|L1],[X|L2]):- sublist(L1,L2)
person levi    schedule 26.01.2015
comment
Порядок имеет значение. Но ваш код не работает для [1,4] и [1,2,3,4] - person Crownless; 26.01.2015
comment
@Crownless хорошо, проверьте мой ответ, вы можете использовать что-то в этом роде. Он вернет True, если первый список является подсписком второго. - person levi; 26.01.2015
comment
Это работает, только если подсписок начинается с первой позиции. Другими словами, `sublist ([1,2,3], [0,1,2,3]) завершится ошибкой. - person schrobe; 26.01.2015
comment
@schrobe Я спросил, имеет ли значение порядок из-за этого. - person levi; 26.01.2015
comment
Тогда это не мой случай, - person Crownless; 26.01.2015

arrow_upward
0
arrow_downward

Я бы использовал добавление:

sublist(X, []) :-
    is_list(X).


sublist(L, [X | Rest]) :-
    append(_, [X|T], L),
    sublist(T, Rest).
person joel76    schedule 26.01.2015

arrow_upward
0
arrow_downward

В принципе, мы можем проверить, является ли M подсписком L, если M существует в L, добавив что-то на его задней и / или передней стороне.

append([], Y, Y).
append([X|XS],YS,[X|Res]) :- append(XS, YS, Res).

sublist(_, []).
sublist(L, M) :- append(R, _, L), append(_, M, R).
person Tacho Jelev    schedule 06.11.2017