Prolog

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

        Р = [а, b, с];

        Р = [а, с, b];

        Р = [b, а, с];

        . . .

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

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

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

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

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

        перестановка( [ ], [ ]).

        перестановка( [X | L ], Р) :-

              перестановка( L, L1),

              внести( X, L1, Р).

Другой вариант этой программы мог бы предусматривать удаление элемента Х из первого списка, перестановку оставшейся его части - получение списка Р, а затем добавление Х в начало списка Р. Соответствующая программа такова:

        перестановка2( [ ], [ ]).

        перестановка2( L, [X | Р] ) :-

              удалить( X, L, L1),

              перестановка2( L1, Р).

Поучительно проделать несколько экспериментов с нашей программой перестановки. Ее нормальное использование могло бы быть примерно таким:

        ?-  перестановка( [красный, голубой, зеленый], Р).

Как и предполагалось, будут построены все шесть перестановок:

        Р = [ красный, голубой, зеленый];

        Р = [ красный, зеленый, голубой];

        Р = [ голубой, красный, зеленый];

        Р = [ голубой, зеленый, красный];

        Р = [ зеленый, красный, голубой];

        Р = [ зеленый, голубой, красный];

        nо                   (нет)

Приведем другой вариант использования процедуры перестановка:

        ?-  перестановка( 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.        Определите отношение

        подмножество( Множество, Подмножество)

где Множество и Подмножество - два списка представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения всех возможных подмножеств заданного множества. Например:

        ?-  подмножество( [а, b, с], S ).

        S = [a, b, c];

        S = [b, c];

        S = [c];

        S = [ ];

        S = [a, c];

        S = [a];

        . . .

Посмотреть ответ

3. 9.    Определите отношение