Пример построения алгоритма

Рассмотрим следующую задачу: построить алгоритм, формирующий всевозможные сочетания без повторений из символов (объектов), заданных множеством M ={ a₁, a₂, …, a_N }, за исключением тривиальных случаев отсутствия символов либо наличия всех символов.

Данный алгоритм может быть представлен как процедура построения собственного подмножества В множества А ={ 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=С^L_n. При выходе из цикла подмножеств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 = C¹₅ = 5

Q’1 = {a, b, c, d}; S1 = C¹₄ = 4

L = 2: Q2 = {ab, ac, ad, ae, bc, bd, be, cd, ce, de }; S = C²₅ = 10

Q’2 = {ab, ac, ad, bc, bd, cd}; S1 = C²₄ = 6

L = 3: Q3 = {abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde }; S = C³₄ = 10

Q’3 = {abc, abd, acd, bcd}; S1 = C³₄ = 4

L = 4: Q4 = {abcd, abce, abde, acde, bcde }; S = C⁴₄ = 5

Q’4 = {abcd}; S1 = C⁴₄ = 1

L = 5: Q5 = {abcde} - исключаем из рассмотрения.

Проведём краткий анализ построенного алгоритма и определим оценки его временной и ёмкостной сложности.