Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Перестановки





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

?- permutation ([a,b,c,r P). Р = [а,Ь,с];

Р Р

[а,с,Ь]; [Ь,а,С];

Программа для отношения permutation может быть снова сформирована исходя из анализа двух описанных ниже случаев, в зависимости от первого списка.

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

2. Если первый список не пуст, то он имеет форму [X | L] и перестановку тако­го списка можно сформировать, как показано на рис. 3.5, — вначале выполнить перестановку L, получив L1, а затем вставить X в любую позицию списка L1.

сформировать перестановку L


       
 
   
 

L1
С^г

L1 - перестановкаL

вставить X, получив перестановку [ X | L ]


Рис. 3.5. Один из способов формирования пере­становки списка [х | L]

Ниже приведены два предложения Prolog, которые соответствуют этим двум случаям.



Часть I. Язык Prolog


permutation ([], [ j). permutation ([X | Lj, P):-

permutation С Ь, 11),

insert! X, LI, P).

Один из альтернативных подходов к разработке этой программы может преду­сматривать удаление одного из элементов (X) из первого списка, перестановку остав­шегося списка с получением списка Р, а затем добавление X перед списком Р. Соот­ветствующая программа выглядит следующим образом:

permutation2 С [],[])• permutations (L, [X j P]):-

del{ X, 1, LI),

permutation2{ Ll, p),

Целесообразно провести некоторые эксперименты с этими программами переста­новки. Обычный способ вызова их на выполнение выглядит примерно так:?- permutation! [ red, blue, green], P).

В соответствии с поставленной задачей должны быть получены все шесть пере­становок следующим образом:

? = I red, blue, green];

р = [ red, green, " blue];

p = [ blue, red, green];

p = [ blue, green, red;;

p = [ green, red, blue);

p= I green, blue, red];
no

Еще одна попытка использовать отношение permutation может состоять в сле­дующем:?- permutation{ L, [a,b,c]).

Теперь первая версия этого отношения, permutation, успешно конкретизирует переменную L всеми шестью значениями перестановок. А если после этого пользова­тель затребует дополнительные решения, программа так и не ответит "по", посколь­ку войдет в бесконечный цикл, пытаясь найти еще одну перестановку, притом что таковая отсутствует. Вторая версия, permutation2, в этом случае найдет только первую (идентичную) перестановку, а затем сразу же войдет в бесконечный цикл. Поэтому при использовании этих программ получения перестановок необходимо со­блюдать осторожность.





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 383 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Надо любить жизнь больше, чем смысл жизни. © Федор Достоевский
==> читать все изречения...

2355 - | 2039 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.007 с.