Программирование на языке Пролог для искусственного интеллекта | страница 51

> удалить( X, БольшийСписок, Список).

В >принадлежит1 мы изящно реализовали отношение принадлежности через >конк. Для проверки на принадлежность можно также использовать и >удалить. Идея простая: некоторый X принадлежит списку >Список, если X можно из него удалить:

>принадлежит2( X, Список) :-

> удалить( X, Список, _ ).

Рассмотрим теперь отношение >подсписок. Это отношение имеет два аргумента — список L и список S, такой, что S содержится в L в качестве подсписка. Так отношение

>подсписок( [c, d, e], [a, b, c, d, e, f] )

имеет место, а отношение

>подсписок( [c, e], [a, b, c, d, e, f] )

нет. Пролог-программа для отношения >подсписок может основываться на той же идее, что и >принадлежит1, только на этот раз отношение более общо (см. рис. 3.4).

Рис. 3.4. Отношения >принадлежит и >подсписок.

Его можно сформулировать так:

 S является подсписком L, если

  (1) L можно разбить на два списка L1 и L2 и

  (2) L2 можно разбить на два списка S и L3.

Как мы видели раньше, отношение >конк можно использовать для разбиения списков. Поэтому вышеприведенную формулировку можно выразить на Прологе так:

>подсписок( S, L) :-

> конк( L1, L2, L),

> конк( S, L3, L2).

Ясно, что процедуру >подсписок можно гибко использовать различными способами. Хотя она предназначалась для проверки, является ли какой-либо список подсписком другого, ее можно использовать, например, для нахождения всех подсписков данного списка:

>?-  подсписок( S, [а, b, с] ).

>S = [];

>S = [a];

>S = [а, b];

>S = [а, b, с];

>S = [b];

>...

Иногда бывает полезно построить все перестановки некоторого заданного списка. Для этого мы определим отношение >перестановка с двумя аргументами. Аргументы — это два списка, один из которых является перестановкой другого. Мы намереваемся порождать перестановки списка с помощью механизма автоматического перебора, используя процедуру >перестановка, подобно тому, как это делается в следующем примере:

>?- перестановка( [а, b, с], P).

>P = [а, b, с];

>P = [а, с, b];

>P = [b, а, с];

>...

Рис. 3.5. Один из способов построения перестановки списка >[X | L].

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

(1) Если первый список пуст, то и второй список должен быть пустым.

(2) Если первый список не пуст, тогда он имеет вид >[X | L], и перестановку такого списка можно построить так, как это показано на рис. 3.5: вначале получить список L1 — перестановку L, а затем внести X в произвольную позицию L1.