Лекция: ПРОГРАММА ВЫЧИСЛЕНИЯ ПЕРЕСТАНОВОК БЕЗ ПОВТОРЕНИЙ

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

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

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

Перестановка из n-элементного множества М есть упорядоченный набор длины n, составленный из попарно различных элементов множества М. Обозначим через PM множество всех перестановок из n элементов и через Pn число всех перестановок из n элементов. Например, если M={a,b,c}, то PM={(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)}; Pn=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 пуст.