можно использовать для разбиения списков. Поэтому вышеприведенную формулировку можно выразить на Прологе так:
подсписок( S, L) :-
конк( L1, L2, L),
конк( S, L3, L2).
Ясно, что процедуру
подсписок
можно гибко использовать различными способами. Хотя она предназначалась для проверки, является ли какой-либо список подсписком другого,
ее можно использовать, например, для нахождения всех подсписков данного списка:
?- подсписок( S, [а, b, с] ).
S = [];
S = [a];
S = [а, b];
S = [а, b, с];
S = [b];
...
3.2.6. Перестановки
Иногда бывает полезно построить все перестановки некоторого заданного списка. Для этого мы определим отношение
перестановка
с двумя аргументами. Аргументы — это два списка, один из которых является перестановкой другого. Мы намереваемся порождать перестановки списка с помощью механизма автоматического перебора, используя процедуру
перестановка
, подобно тому, как это делается в следующем примере:
?- перестановка( [а, b, с], P).
P = [а, b, с];
P = [а, с, b];
P = [b, а, с];
...
Рис. 3.5. Один из способов построения перестановки списка
[X | L]
.
Программа для отношения
перестановка
в свою очередь опять может основываться на рассмотрении двух случаев в зависимости от вида первого списка:
(1) Если первый список пуст, то и второй список должен быть пустым.
(2) Если первый список не пуст, тогда он имеет вид
[X | L]
, и перестановку такого списка можно построить так, как это показано на рис. 3.5: вначале получить список L1 — перестановку L, а затем внести X в произвольную позицию L1.
Два прологовских предложения, соответствующих этим двум случаям, таковы:
перестановка( [], []).
перестановка( [X | L ], P) :-
перестановка( L, L1),
внести( X, L1, P).
Другой вариант этой программы мог бы предусматривать удаление элемента X из первого списка, перестановку оставшейся его части — получение списка P, а затем добавление X в начало списка P. Соответствующая программа такова:
перестановка2( [], []).
перестановка2( L, [X | P] ) :-
удалить( X, L, L1),
перестановка2( L1, P).
Поучительно проделать несколько экспериментов с нашей программой перестановки. Ее нормальное использование могло бы быть примерно таким:
?- перестановка( [красный, голубой, зеленый], P).
Как и предполагалось, будут построены все шесть перестановок:
P = [ красный, голубой, зеленый];
P = [
красный, зеленый, голубой];
P = [ голубой, красный, зеленый];
P = [ голубой, зеленый, красный];
P = [ зеленый, красный, голубой];
P = [ зеленый, голубой, красный];
no
(нет)
Приведем другой вариант использования процедуры
перестановка
:
?- перестановка( L, [а, b, с] ).
Наша первая версия,
перестановка
, произведет успешную конкретизацию L всеми шестью перестановками. Если пользователь потребует новых решений, он никогда не получит ответ "нет", поскольку программа войдет в бесконечный цикл, пытаясь отыскать новые несуществующие перестановки. Вторая версия,
перестановка2
, в этой ситуации найдет только первую (идентичную) перестановку, а затем сразу зациклится. Следовательно, при использовании этих отношений требуется соблюдать осторожность.
Упражнения
3.3. Определите два предиката
четнаядлина( Список)
и
нечетнаядлина( Список)
таким образом, чтобы они были истинными, если их аргументом является список четной или нечетной длины соответственно. Например, список
[а, b, с, d]
имеет четную длину, a
[a, b, c]
— нечетную.
3.4. Определите отношение
обращение( Список, ОбращенныйСписок)
,
которое обращает списки. Например,
обращение( [a, b, c, d], [d, c, b, a] ).
3.5. Определите предикат
палиндром( Список).
Список называется палиндромом, если он читается одинаково, как слева направо, так и справа налево. Например,
[м, а, д, а, м]
.
3.6. Определите отношение
сдвиг( Список1, Список2)
таким образом, чтобы
Список2
представлял собой
Список1
, "циклически сдвинутый" влево на один символ. Например,
?- сдвиг( [1, 2, 3, 4, 5], L1),
сдвиг1( LI, L2)
дает
L1 = [2, 3, 4, 5, 1]
L2 = [3, 4, 5, 1, 2]
3.7. Определите отношение
перевод( Список1, Список2)
для перевода списка чисел от 0 до 9 в список соответствующих слов. Например,
перевод( [3, 5, 1, 3], [три, пять, один, три] )
Используйте в качестве вспомогательных следующие отношения:
означает( 0, нуль).
означает( 1, один).
означает( 2, два).
...
3.8. Определите отношение
подмножество( Множество, Подмножество)
где
Множество
и
Подмножество
— два списка представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения всех возможных подмножеств заданного множества. Например: