Программа вычисления перестановок БЕЗ повторений

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

ЦЕЛЬ: Познакомиться с реализацией основных комбинаторных схем на языке пролог и научиться писать программы по их генерации.

ПРОГРАММА ВЫЧИСЛЕНИЯ ПЕРЕСТАНОВОК БЕЗ ПОВТОРЕНИЙ

Перестановка из n-элементного множества М есть упорядоченный набор длины n, составленный из попарно различных элементов множества М. Обозначим через P_M множество всех перестановок из n элементов и через P_n число всех перестановок из n элементов. Например, если M={a,b,c}, то P_M={(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)}; P_n=6.

Процедура permulation(A,L) строит список L всех перестановок алфавита А. Например, если А=[a,b,c], то

L=[[a,b,c],[b,a,c],[b,c,a],[a,c,b],[c,a,b],[c,b,a]].

Процедура permut(A,P) выдает перестановку P алфавита А. Например, если А=[a,b,c], то программа выдаст:

P=[a,b,c] →;

P=[b,a,c] →;

P=[b,c,a] →;

P=[a,c,b] →;

P=[c,a,b] →;

P=[c,b,a] →;

no

Процедура insert(X,P,L) символ X “пропускает” через список L и выдает результат P. Например, если X=a, L=[1,2,3], то результат будет следующий:

P=[a,1,2,3] →;

P=[1,a,2,3] →;

P=[1,2,a,3] →;

P=[1,2,3,a] →;

no

Текст программы:

d(A,L):-permulation(A,L).

permulation(A,L):-findall(P,permut(A,P),L).

permut([],[]).

permut([X|L],P):-permut(L,L1),insert(X,P,L1).

insert(X,[X|T],T).

insert(X,[Y|T],[Y|T1]):-insert(X,T,T1).

insert(X,[],[X]).

Встроенный предикат findall( Template , Goal , Bag ) принимает значение успешно, если Bag – есть список всех тех переменных из спискаTemplate, для которых цель Goal успешна. Список Bag не упорядочивается, повторы элементов не устраняются. Если объектов удовлетворяющих цели нет, то запрос истинен, если список Bag пуст.