Рассмотрим следующую задачу: построить алгоритм, формирующий всевозможные сочетания без повторений из символов (объектов), заданных множеством M ={ a1, a2, …, aN }, за исключением тривиальных случаев отсутствия символов либо наличия всех символов.
Данный алгоритм может быть представлен как процедура построения собственного подмножества В множества А ={ Q0, Q1, …, QN }, где QJ – множества элементов (наборов) всевозможных сочетаний без повторений из N по J символов из M, 
. Напоминаем, что в собственное подмножество не входят как пустое, так и полное подмножества, т. е. В Í А, B ¹ Q0 =Æ, В ¹ QN.
При разработке алгоритма воспользуемся методом "сверху-вниз" [2]. Очевидно, алгоритм должен включать в себя ввод исходного множества M символов, инициализацию, т.е. подготовительную фазу процесса решения задачи: вычисление констант, параметров, например, циклов, предварительное преобразование данных и представление их в удобной форме и т. п., процедуру PAQ формирования всех подмножеств QJ, 
наборов, а также вывода сформированных подмножеств (рис. 5.2,а).
Далее заметим, что если подмножества сгруппировать по признаку одинаковой длины L наборов, то вывод сформированного подмножества QL с наборами длины L может быть произведен в цикле по L (рис. 5.2,б). Это даёт экономию памяти по сравнению с первым вариантом алгоритма. Процедуру формирования подмножества наборов длины L назовём PQL.
Рассмотрим один из возможных способов формирования подмножества QL. Очевидно, что новое подмножество (назовём его NQ) может быть получено из предыдущего дописыванием к его элементам символов из множества M. При этом нужно учесть, что если элемент q Î QL содержит последний символ ls (last symbol), ls=M[N], то к нему уже больше нечего дописывать. Поэтому имеет смысл из подмножества QL образовать подмножество Q'L, не содержащее элементов, последний символ p которых совпадает с ls; элементы, у которых p=ls, будем называть особыми, а процедуру удаления особых элементов будем называть DEL. Процедуру дописывания к выбранным из подмножества Q'L элементам q символов x Î M назовём INS. Тогда процедура формирования нового подмножества NQ из подмножества QL может быть реализована последовательным применением процедур DEL и INS (рис. 5. 2,в).
Более тщательное рассмотрение этих процедур показывает, что изолированная реализация каждой из них является избыточной по временной сложности, так как и в первой, и во второй процедурах используется перебор в цикле элементов подмножеств QL и Q'L, но поочередно. Поэтому целесообразно организовать общий для них цикл по К, где К - номер элемента q Î QL (рис.5.2,г). Тогда эти процедуры необходимо несколько изменить и увязать их в общем цикле (рис. 5.2,д); число повторений цикла определяется количеством элементов в подмножестве QL: S=СLn. При выходе из цикла подмножествo NQ следует переименовать в QL, т. е. переписать содержимое файла с именем NQ в файл с именем QL (NQ обнуляется).
В процедуре DEL теперь будет решаться вопрос: "Удалить элемент q=QL [ K ]?"; в случае положительного ответа процедура INS для элемента q не выполняется. Удаление элемента q осуществляется по признаку cовпа-дения символов: p=ls (предварительно для q определяется его последний символ - Last Symbol of the Element - p = LSE(q)). Этот фрагмент СА представлен на рис. 5.2,д. В случае отрицательного ответа элемент q обрабатывается процедурой INS, где на его основе формируются новые элементы множества NQ. Отметим здесь же, что имеет смысл вынести из цикла по К и по L определение ls, как не зависящее от параметров этих циклов.
Рассмотрим процедуру INS. Должно быть ясно, что к элементу q надо дописывать не все символы х Î M, а только те, которые в множестве M идут после символа, совпадающего с последним символом р элемента q. Так, если M ={ a,b,c,d,e } и q = ab, то LSE(q)= b, и x Î{ c,d,e }. Обозначим NM множество следующих за р символов из множества M; для данного примера NM ={c,d,e}. Тогда процедура PNM - это формирование множества NM, которое получается исключением из М всех символов слева до р включительно. Далее можно непосредственно реализовать в цикле по I (I - номер символа в множестве NМ) процедуру дописывания по одному символу х Î NМ к элементу q, пока выбранный из NМ символ не окажется последним; полученные новые элементы заносятся в множество NQ слева направо. Затем производится переименование множества (QL:= NQ). Этот фрагмент СА представлен на рис. 5.2,е.
Отметим, что процедуры LSE, РNМ, а также операции занесения элемента в множество пока не определены. Конкретная их реализация зависит от выбора структуры данных; доработать данный алгоритм с учётом выбранных структур данных можно самостоятельно. "За бортом" остались также вопросы формирования имени подмножества, переменной длины подмножества, ввода и вывода данных; решение этих вопросов в большей мере определяется языком программирования.
"Соберём" схему алгоритма из отдельных, уже продуманных фрагментов. При этом с целью стыковки фрагментов СА в неё включены дополнительные блоки: блоки инициализации всех циклов (L:=1; K:=0; I:=0), блоки общей инициализации (ls:= A [ N ]- это константа; NQ:= М - для единообразия обработки подмножества Q1); блок вывода QL переставлен в начало цикла по L с целью единообразия обработки всех подмножеств QL, включая Q1.
Схему алгоритма построения собственного подмножества, составленного из фрагментов СА с учётом их стыковки и замечаний о неполноте проработки, можно получить самостоятельно.
 |
Рассмотрим контрольный пример. Пусть задано множество символов М = {a, b, c, d, e}; последний элемент этого множества ls = e. Имеем (выделены особые элементы)
Q0 = Æ - исключаем из рассмотрения; Число элементов
L = 1: Q1 = {a, b, c, d, e } = M; S = C15 = 5
Q’1 = {a, b, c, d}; S1 = C14 = 4
L = 2: Q2 = {ab, ac, ad, ae, bc, bd, be, cd, ce, de }; S = C25 = 10
Q’2 = {ab, ac, ad, bc, bd, cd}; S1 = C24 = 6
L = 3: Q3 = {abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde }; S = C34 = 10
Q’3 = {abc, abd, acd, bcd}; S1 = C34 = 4
L = 4: Q4 = {abcd, abce, abde, acde, bcde }; S = C44 = 5
Q’4 = {abcd}; S1 = C44 = 1
L = 5: Q5 = {abcde} - исключаем из рассмотрения.
Проведём краткий анализ построенного алгоритма и определим оценки его временной и ёмкостной сложности.