Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Иногда бывает полезно построить все перестановки некоторого заданного списка. Для этого мы определим отношение перестановка с двумя аргументами. Аргументы — это два списка, один из которых является перестановкой другого. Мы намереваемся порождать перестановки списка с помощью механизма автоматического перебора, используя процедуру перестановка, подобно тому, как это делается в следующем примере:
?- перестановка([а, 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, в этой ситуации найдет только первую (идентичную) перестановку, а затем сразу зациклится. Следовательно, при использовании этих отношений требуется соблюдать осторожность.
Дата публикования: 2015-10-09; Прочитано: 150 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!