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

Сочетание из n элементов по r есть r – элементное подмножество n – элементного множества M.

Обозначим через CrM множество всех сочетаний из n элементов по r и через Crn число всех сочетаний из n элементов по r. Например, если M={a,b,c}, то C1M={(a),(b),(c)},C2M={(a,b),(a,c),(b,c)};C13=|C1M|=3;C23=|C2M|=3.

Процедура combination(A,R,C) строит множество С всех сочетаний элементов алфавита A по R элементов в каждом сочетании.

Процедура combin2(A,C1) строит множество С всех сочетаний элементов алфавита А по 2 элемента в каждом сочетании.

Процедура combinK(C1,A,R,K,C), исходя из множества С1 всех сочетаний элементов алфавита А по 2, последовательно строит множества сочетаний по K=3,4,…,R элементов.

Процедура combinK_K1(C1,A,C), исходя из множества C1 всех сочетаний элементов алфавита А по K, строит множество всех сочетаний элементов алфавита A по K+1. Вычисление осуществляются с помощью процедуры comb(C1,A,Ac,C), содержащую переменную-накопитель Ac. Пусть, например, C1=[[a,b,c],[a,b,d],[a,d,e],[a,c,d],[a,c,e],[a,d,e],[b,c,d],[b,c,e],[b,d,e],[c,d,e]], A=[a,b,c,d,e].

Берем элемент а из А. собираем в С1 все сочетания, содержащие элемент а. выбрасываем их из С1 и к каждому сочетанию результата С2=[[b,c,d],[b,c,e],[b,d,e],[c,d,e]] приписываем спереди элемент а. Результата помещаем в накопитель Ac. Берем элемент b из А и проделываем аналогичную операцию для С2 и b. Результат приписываем в накопителе Ac. И так далее до исчерпания множества C1. В накопителе Ас будут собраны все сочетания из А по 4.

d(A,R,C):-A=[a,b,c,d,e],combination(A,R,C).

combination(A,R,C):-length(A,L),(R=0;R>L),C=[].

combination(A,R,C):-length(A,L),R=1,C=A.

combination(A,R,C):-length(A,L),R\=0,R\=1,R<L+1,combin2(A,C1),combinK(C1,A,R,2,C).

combin2(A,C1):-combin2_rep(A,[],C1).

combin2_rep([H|T],Ac,C):-findall([H,X],member(X,T),L),