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

Иногда возникает необходимость найти все возможные перестановки элементов в заданном списке. Для этого определим отношение 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, в этом случае найдет только первую (идентичную) перестановку, а затем сразу же войдет в бесконечный цикл. Поэтому при использовании этих программ получения перестановок необходимо со­блюдать осторожность.