Генерация комбинаторных объектов

Реферат Генерация комбинаторных объектов Содержание Введение 1 Множество всех подмножеств 2 Перестановки 3 Сочетания 4 Размещения 5 Перестановки с повторениями 6 Сочетания с повторениями 20 Заключение 23 Литература 24 Введение Существует набор задач, решение которых заключается в генерации всех элементов таких комбинаторных

объектов как множество всех подмножеств, перестановки, сочетания, размещения, перестановки с повторениями, сочетания с повторениями. Для каждого сгенерированного элемента затем проверяются какие-то свойства для конкретной задачи. В дальнейшем в данной работе предлагается следующий порядок изложения материала для каждого комбинаторного объекта: пример, алгоритм, программа, комментарии к программе. 1 Множество всех подмножеств Пусть мы имеем множество из 4-х компонент - которые мы обозначаем латинскими

буквами A, B, C, D соответственно. И пусть по условиям задачи требуется выбрать подмножество, состоящее из нескольких компонент, обладающее некоторым свойством. Предлагается такой способ решения задачи: мы генерируем ВСЕ возможные подмножества данного множества и для каждого из сгенерированных подмножеств проверяем удовлетворяет ли оно заданному свойству. Альтернативный вариант задачи - подсчитать

ВСЕ подмножества данного множества, обладающие заданным свойством. Например: Для множества из 4-х символов A,B,C,D множество всех подмножеств включает в себя следующие множества: Пустое множество Одноэлементные множества: {A}, {B}, {C}, {D} Двухэлементные множества: {A,B}, {A,C}, {A,D} {B,C}, {B,D}, {C,D} Трехэлементные множества: {A,B,C}, {A,B,D}, {A,

C,D}, {B,C,D} Четырехэлементное множество: {A,B,C,D} В случае, если порядок генерации подмножеств не играет роли (а, например, в случае необходимости подсчитать все подмножества, обладающие заданным свойством, так оно и есть) один из наиболее просто кодируемых алгоритмов генерации множества всех подмножеств выглядит следующим образом. Заведем вектор B, состоящий из четырех чисел, каждое из которых может принимать значение 0 или 1.

И будем считать, что значение 1 указывает на то, что соответствующий по номеру компонент исходного множества включается в множество, а значение 0 указывает на то, что элемент не включается. Рассмотрим теперь последовательность двоичных чисел от 0 до 15 и соответствующие им подмножества: 4321 DCBA 0000 - Пустое множество 0001 A 0010 B 0011 AB 0100 C 0101 AC 0110 BC 0111 ABC 1000 D 1001 AD 1010

BD 1011 ABD 1100 CD 1101 ACD 1110 BCD 1111 ABCD Таким образом, всего имеется 16 различных подмножеств множества из 4-х элементов. В общем случае множество всех подмножеств множества из N элементов содержит 2N (два в степени N) элементов. Алгоритм, обеспечивающий такую генерацию множества всех подмножеств из N элементов, может быть неформально описан следующим образом:

Формируем массив, состоящий из N нулей - и рассматриваем его как пустое множество. Таким образом, начальное значение текущего подмножества - пустое множество. Для получения следующего подмножества из текущего подмножества обрабатываем текущий массив из чисел 0 или 1 следующим образом: Справа (от первого элемента массива к последнему) ищем первое число, равное нулю. Если такое число не найдено - значит, текущее подмножество является последним - множеством, состоящим

из всех элементов, и на этом алгоритм заканчивает свою работу. Если же элемент равный 0 найден, то он заменяется на 1, а все числа справа от него (если таковые имеются) заменяются на нули. Более формализовано этот алгоритм может быть записан следующим образом: Ввод (N) Обнуление массива B из N+1 элемента Вывод (Пустое множество) Пока B[N+1]=0 i=1 Пока B[i]=1 делать B[i]=0, i=i+1

B[i]=1 Вывод (множества, определяемого массивом B) Ниже приводится текст программы, которая считывает N - число элементов в множестве и выводит на экран множество всех подмножеств обозначая элементы соответствующими по порядку латинскими буквами: const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1 100] of byte; N,i : byte; begin readln(N); for i:=1 to

N+1 do b[i]:=0; writeln ('Пустое множество'); while (b[N+1]=0) do begin i:=1; while B[i]=1 do begin B[i]:=0; inc(i); end; B[i]:=1; for i:=1 to n do if b[i]=1 then write(alphabet[i]); writeln; end; end. При необходимости обрабатывать (анализировать) построенные подмножества могут быть добавлены вызовы процедур обработки, получающие в качестве параметра массив B (указывающий своими единичными элементами номера элементов множества, включенных в текущее подмножество).

2 Перестановки Пусть мы имеем 4 компонента, обозначенные буквами A, B, C, D соответственно. Тогда множество всех перестановок из этих компонент будет включать следующие элементы: ABCD BACD CABD DABC ABDC BADC CADB DACB ACBD BCAD CBAD DBAC ACDB BCDA CBDA DBCA ADBC BDAC CDAB DCAB ADCB BDCA CDBA DCBA Проиллюстрируем сначала алгоритм построения следующей перестановки на примере перестановок

из 9 компонент, обозначенных соответственно цифрами от 1 до 9. Первая из таких перестановок это 9 Пусть текущая перестановка из 9 компонент: 2 Каким будет следующее значение перестановки, если мы строим ее в лексикографическом порядке (то есть в порядке возрастания величины числа, составленного из этих цифр)?

Правильный ответ таков : 1 9 5 8 6 2 3 4 7 Как он получается? Прежде всего, необходимо просматривать исходный массив от конца к началу, что бы найти первое число, которое МЕНЬШЕ предыдущего в нашем случае - это 4 (7>6>3>2, а 4<7) Далее среди просмотренных чисел справа от найденной 4 мы ищем последнее число которое больше 4. Это число 6. (7>4, 6>4, 3<4, 2<4) Затем меняем эти 2 найденных числа (4 и 6) местами, получаем:

2 И теперь числа (справа от 6), которые составляют убывающую последовательность (7 4 3 2) , попарно меняем местами так, что бы они составили возрастающую последовательность (2 3 4 7) : 1 9 5 8 6 2 3 4 7 Это и есть следующая перестановка. А какая перестановка будет последней для данного примера? Надеюсь, что вдумчивый читатель догадался и сам: 9 8 7 6 5 4 3 2 1

Несколько неформально алгоритм построения следующей перестановки по текущей может быть записан следующим образом: 1. От конца к началу перестановки ищем первый элемент B[i] такой, что B[i]<B[i+1] запоминаем его индекс - I 2. От элемента I+1 до конца ищем последний элемент, больший чем B[i], запоминаем его индекс - K 3. Меняем местами эти элементы - с номерами

I и K 4. Всю группу элементов от i+1-го элемента до N-го попарно меняем местами (i+1-ый элемент с N-ым, i+2-ой элемент с N-1-ым и т.д.) Формализовано алгоритм генерации всех перестановок из N элементов может быть записан следующим образом: Ввод N Прописываем массив B последовательно числами от 1 до

N Это первая - начальная - перестановка, выводим ее Пока (истина) i=N Пока (i>0) и (B[i]>=B[i+1]), i=i-1 Если i=0 то конец работы Для j от i+1 до N если B[j]>B[i] то K=j Обмен значений B[i] и B[k] Для j от i+1 до (i+ ((N+1-i) div 2)) Обмен значений B[j] и B[N+i+1-j] Вывод текущей перестановки

B Понятно, что цикл попарных перестановок "хвоста" массива B нельзя делать от i+1 до N-го элемента - иначе элементы поменяются местами по 2 раза - и получиться, что ничего не изменилось. Цикл нужно выполнить для половины этого "хвоста". Этому и служит несколько сложное для понимания значение конечной переменной цикла: i+ (N+1-i) div 2 Ниже приводится программа, генерирующая все перестановки из

N компонент, обозначенных N первыми буквами латинского алфавита. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1 100] of byte ; N,i,j,k : byte; Procedure SwapB(i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure WriteB; begin for i:=1 to N do write({alphabet[b[i]]); writeln; end; begin readln(N); for i:=1 to

N do b[i]:=i; WriteB; while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j); writeB; end; end. В программе введены 2 процедуры WriteB и SwapB. Процедура WriteB вызывается всякий раз, когда построена очередная перестановка.

В данной программе процедура WriteB просто выводит соответствующую последовательность латинских букв. Процедура SwapB(i,k) введена для упрощения понимания главной программы. SwapB просто обменивает значениями два элемента массива B - те, которые имеют индексы, соответствующие значениям параметров процедуры i и k. Процедура SwapB используется в тексте программы два раза 1)

При обмене значениями двух найденных элементов с индексами I и K. 2) При обеспечении попарного обмена элементов "хвоста", в котором текущий элемент с индексом j обменивается местами со своим "партнером", находящимся на позиции N+i+1-j. Таким образом, I+1-ый элемент поменяется (при J=I+1) местами с N-м элементом, I+2-ой элемент (при

J=I+2) с N-1-ым и т.д. Общее число перестановок из N элементов равно N! (читается N факториал). Напомним, что N! = 1*2*3* *N 3 Сочетания Пусть имеем 5 компонент, обозначенных латинскими буквами A, B, C, D, E соответственно. Тогда все сочетания из этих 5 компонент по 3, выписанные в лексикографическом порядке (для букв и цифр от 1 до 5) будут таковы: ABC 123

ABD 124 ABE 125 ACD 134 ACE 135 ADE 145 BCD 234 BCE 235 BDE 245 CDE 345 Неформально алгоритм генерации последовательности чисел в лексикографическом порядке можно записать следующим образом. Выберем наименьшие M из имеющихся N чисел и выпишем их в порядке возрастания - и выпишем их в порядке возрастания - 1 2 3 - это начальное сочетание. Очевидно, что наибольшие

M чисел из имеющихся (3 4 5), выписанные в порядке возрастания, составят последнее сочетание. Для того, что бы по текущему сочетанию получать следующее, можно поступать следующим образом: Находим позицию в текущем сочетании, на которой не стоит последнее из возможных значений, и затем увеличиваем его на 1. А все последующие элементы сочетания получаем увеличением на 1 предыдущего элемента сочетания. Например пусть текущее сочетание 1 3 5 Анализ начинаем с последней позиции сочетания.

5 - это последнее возможное значение, потому переходим к предыдущей позиции. 3 - это не последнее возможное значение для этой позиции (каковым является 4 в данном случае). Потому мы его увеличиваем на 1 - получаем 4. А число в следующей позиции получаем прибавлением 1 к этой 4-ке - и получаем 5. Таким образом следующее значение будет 1 4 5 Более формализовано этот алгоритм может быть записан следующим образом:

Ввод N, M (из сколька, по сколько) Заносим в массив B числа от 1 до M Это первое сочетание, выводим его Пока (истина) i=M Пока (i>0) и (b[i]=N-m+i), i=i-1 Если i=0 то работа завершена B[i]=B[i]+1 Для j от i+1 до M B[j]=B[j-1]+1; Вывод B - следующей перестановки Ниже приводится программа, которая считывает с клавиатуры

значения N и M и выводит в лексикографическом порядке все сочетания из N первых латинских букв по M. uses crt; const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1 100] of byte; N,M,i,j,k : byte; Procedure WriteB; begin for i:=1 to M do write(alphabet[b[i]]); writeln; end; begin readln(N,M); for i:=1 to M do b[i]:=i; WriteB; while (true) do begin i:=M; while (i>0) and (b[i]=N-m+i) do

Dec(i); if i=0 then exit; Inc(B[i]); for j:=i+1 to M do B[j]:=B[j-1]+1; WriteB; end; end. Напомним, что общее число сочетаний из N элементов по M может быть вычислено по формуле C (N,M) = N! / (M! * (N-M)! ) 4 Размещения Для генерации всех размещений из N элементов по M можно воспользоваться композицией алгоритмов, изложенных выше.

То есть генерировать все сочетания из N по M, а затем для каждого полученного сочетания генерировать все перестановки из M элементов. Например, при генерации всех размещений из 5 элементов по 3, в случае, если сами элементы обозначены латинскими буквами A,B,C,D,E нужно получить следующую последовательность, представленную для компактности в виде 10 строк, каждая из которых представляет все возможные сочетания из 3 букв первого элемента строки.

А сами первые элементы строк как раз и представляют все возможные сочетания из 5 букв по 3. ABC ACB BAC BCA CAB CBA ABD ABE ACD ACE ADE BCD BCE BDE CDE CED DCE DEC ECD EDC Общее количество pазмещений - из N элементов по M может быть найдено по формуле: N! / (N-M)! Ниже приводится программа, которая вводит с клавиатуры числа

N, M и генерирует все возможные размещения из N букв по M. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; type barray = array [1 100] of byte; var b : barray; N,M,i,j,k : byte; z : longint; Procedure WriteB(B:barray); begin Inc(Z); Write (Z:3 : '); for i:=1 to M do write(alphabet[b[i]]); writeln; end; Procedure

SwapB(var B:barray;i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure PermuteAll(B:barray;N:byte); var i,k,j : byte; begin WriteB(B); while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(B,i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do

SwapB(B,j,N+i+1-j); WriteB(B); end; end; begin readln(N,M); for i:=1 to M do b[i]:=i; PermuteAll(B,M); while (true) do begin i:=M; while (i>0) and (b[i]=N-m+i) do Dec(i); if i=0 then exit; Inc(B[i]); for j:=i+1 to M do B[j]:=B[j-1]+1; PermuteAll(B,M); end; readln; end. Пояснения к программе: 1. Главная программа вводит числа

N, M и генерирует по описанному выше алгоритму все сочетания из N по M. Для каждого построенного в векторе B сочетания вызывается процедура PermuteAll, которой в качестве параметров передаются текущее сочетание B и количество элементов в нем M. Процедура PermuteAll генерирует для полученного сочетания все возможные перестановки. 2. Массив B передается в процедуру PermuteAll по значению (при объявлении процедуры при

параметре B нет ключевого слова VAR) и потому изменения массива B в процедуре PermuteAll не влияют на содержимое массива B в главной программе. 3. В то же время для того, что бы процедура SwapB могла обменивать значения в B и возвращать измененный массив в вызывающую ее процедуру PermuteAll, массив B добавлен в параметры процедуры

SwapB с передачей по адресу - используя ключевое слово VAR. 4. Для передачи массива в качестве параметра заведен специальный тип BARRAY. 5. Для подсчета всех сгенерированных размещений используется переменная Z в процедуре WriteB. 5 Перестановки с повторениями Перестановки с повторениями допускают повторное использование элементов.

Например, пусть имеем множество, состоящее из двух символов A и двух символов B. Тогда все перестановки с повторениями из этих символов будут таковы: AABB ABBA BABA ABAB BAAB BBAA В общем случае, если имеем N1 предметов 1-го вида N2 предметов 2-го вида Nk предметов K-го вида Общее количество перестановок может быть вычислено по формуле

N!/ (N1!*N2!* *Nk!) Алгоритм аналогичен генерации перестановок без повторений за исключением формирования начальной перестановки: i=0; Для j от 1 до k Для m от 1 до N[j] i=i+1; B[i]=j; Ниже приводится программа генерации перестановок с возвращениями. Количество K различных типов предметов, обозначенных латинскими буквами вводится с клавиатуры. С клавиатуры также вводятся количества NN[j] предметов каждого типа.

Сумма введенных NN[j] определяет общее количество элементов в каждой из генерируемых перестановок. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1 100] of byte; N,i,j,k,m : byte; NN : array [1 100] of longint; Procedure SwapB(i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure WriteB; begin for i:=1 to

N do write(alphabet[b[i]]); writeln; end; begin readln(K); N:=0; for i:=1 to K do begin read(NN[i]); N:=N+NN[i]; end; i:=0; for j:=1 to k do for m:=1 to NN[j] do begin Inc(i); B[i]:=j; end; WriteB; while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit; for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do

SwapB(j,N+i+1-j); WriteB; end; end. 6 Сочетания с повторениями Для множества символов от A до C и размера M=3 сочетания с повторениями будут следующими: CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA Общее количество сочетаний = (N+M-1)! / (M!*(N-1)!) где N - количество символов M - по сколько символов в сочетании Основная идея генерации таких сочетаний с повторениями заключается в следующем:

Сочетания записываем в виде (N-1)-го нуля и M единиц ,где единицы заменяют символы, а нули выступают в pоли pазделителей. Напpимеp: ABB - 1 0 1 1 AAC - 1 1 0 0 1 C C C - 0 0 1 1 1 A B B A A C C C C При таком подходе для решения задачи достаточно сгенерировать все перестановки из M единиц и N-1-го нуля. Ниже приводится программа, которая решает поставленную задачу. const alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var b : array [1 100] of byte;

N,i,j,k,M,N1 : byte; Procedure SwapB(i,k:byte); var x : byte; begin x:=B[i]; B[i]:=B[k]; B[k]:=x; end; Procedure WriteB; var i,j : byte; begin j:=1; for i:=1 to N do if b[i]=0 then Inc(j) else write(alphabet[j]); writeln; end; begin readln(N1,M); N:=N1-1+M; for i:=1 to n1-1 do b[i]:=0; for i:=n1 to n1+m-1 do b[i]:=1; WriteB; while (true) do begin i:=N; while (i>0) and (B[i]>=B[i+1]) do i:=i-1; if i=0 then exit;

for j:=i+1 to N do if (B[j]>B[i]) then K:=j; SwapB(i,k); for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j); WriteB; end; end. Пояснения к программе: 1. Начальная перестановка формируется последовательно из N1-1 нулей и M единиц. 2. В программе вывода перестановки WriteB осуществлены изменения, соответствующие замыслу (нули - разделители, единицы - символы).

Если текущий элемент массива B равен 0, то "становится активным" следующий символ. Если текущий символ массива B равен 1, то текущий активный символ выводится на экран. Заключение Все программы для большей наглядности в качестве иллюстрации оперируют с массивом символов от A до Z. Очевидно, что предлагаемые алгоритмы и программы практически не изменяются при работе с массивами элементов любого типа, требуемого по условиям задачи (например, массивами чисел, слов, геометрических

фигур и т.д.) Литература 1. Абдеев Р.Ф. Философия информационной цивилизации М.: Владос, 1994. 2. Адамар Ж. Исследование психологии процесса изобретения в области математики М.: Сов. радио, 1970. 3. Болтянский В.Г. Информатика и преподавание математики// Математика в школе. 1989. № 4 С.86-90 4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум

М.: Радио и связь, 1982. 5. Вирт Н. Алгоритмы+Структуры данных=Программа М.:Мир, 1989 6. Вирт Н. Систематическое программирование: Введение М.: Мир, 1977. 7. Громов Г.Р. Очерки информационной технологии М.: ИнфоАрт, 1993. 8. Дейкстра Э. Дисциплина программирования М.: Мир, 1978. 9. Ильенков Э. В. Философия и культура

М.: Полит. лит 1991. 10. Йодан Э. Структурное проектирование и конструирование программ М.: Мир, 1979. 11. Майерс Г. Надежность программного обеспечения М.: Мир, 1980. 12. Махмутов М.И. Организация проблемного обучения в школе М 1986.