Два прологовских предложения, соответствующих этим двум случаям, таковы:
>перестановка( [], []).
>перестановка( [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)
