ЗАДАЧА О РАЗМЕЩЕНИИ

Рассмотрены методические аспекты преподавания темы в курсе «дискретная математика». Синтезированы в единое целое математические факты и алгоритмические особенности задачи о размещении.

При изучении комбинаторики детально рассматриваются такие объекты, как размещения, сочетания и перестановки (с повторениями и без повторений), появляющиеся при решении общей задачи о выборке k элементов из n элементов конечного множества A={a1,a2, …,an}. Разрешается выбирать с повторениями, то есть один элемент в выборке может присутствовать несколько раз и без повторений. Кроме того, различают выборки упорядоченные и неупорядоченные. В первом случае две выборки, различающиеся порядком следования элементов, считаются различными, во втором – нет. Комбинируя «повторения», «упорядоченность», получаем, в соответствии с принципом умножения, 4 различных случая. Если «прибавить» случай, когда k=n (перестановки), то получаем 6 разновидностей задачи. В табл. 1 резюмирована информация по этой задаче и приводятся формулы для подсчета количества комбинаторных объектов каждого типа. Детальное их рассмотрение можно найти в [1, 2].
Таблица 1

Другому типу задач, а именно, размещению n элементов (предметов) конечного множества А по ящикам (урнам) уделяется в учебной литературе по комбинаторике значительно меньшее внимание. В общем случае ящики могут быть как различимыми (с номерами), так и нет. Следующее условие по ящикам заключается в допущении пустоты или не пустоты содержимого ящиков. Другими словами, при размещении предметов по ящикам нет пустых ящиков или есть. Если пустых ящиков нет, то такое размещение трактуется как разбиение n предметов на k блоков. Обозначим количество таких разбиений как S(n,k) и приведем сводную таблицу логически возможных вариантов задачи о размещении (табл. 2).
Таблица 2

В первой строке табл. 2 описан случай размещения n различных предметов по k различным ящикам, причем некоторые из ящиков могут быть пустыми. Каждый из предметов размещается k способами, общее количество размещений, согласно принципу умножения, k*k*…*k (перемножаем n раз) – kn.
В третьей строке табл. 2 предметы неразличимы, ящики различимы и допускаются пустые ящики. Обозначим конкретное размещение как aa aaa …aaa a…aa…a, где общее количество букв а равно n, а разделитель «» показывает – сколько предметов находится в конкретном ящике. Если два разделителя находятся рядом, то в соответствующем ящике нет предметов. Количество разделителей k 1. Общая длина последовательности из букв a и  равна n+k 1. Количество способов выбора мест для разделителей равно ???.
Четвертая строка отличается от третьей только тем, что не допускаются пустые ящики. Разложим по одному предмету в каждый ящик. Останется n k предметов и для них решается предыдущая задача – ???.
Нерассмотренными остались строки 2, 5 и 6 табл. 2. Однако, задача, описываемая строкой 6 табл. 2 является ключевой. Если мы умеем размещать (разбивать) n предметов по k ящикам (блокам), при этом пустых ящиков нет, то тем самым, мы умеем решать и оставшиеся две задачи. Действительно. Случай два отличается от шестого тем, что ящики различимы. Это значит, что из каждого S(n,k) способов можно получить еще k! способов, перекладывая предметы, задаваемые этим способом, по различимым ящикам – общее количество способов равно k!S(n,k). Случай пять отличается от шестого тем, что допускаются пустые ящики. Он сводится к шестому следующим образом: все n предметов складываются в один ящик – количество способов S(n,1); все n предметов раскладываются по двум ящикам – S(n,2); …; все n предметов размещаются по k ящикам. Общее количество – S(n,1)+S(n,2)+…+S(n,k).
Итак, рассмотрим задачу о разбиении n различимых предметов на k блоков. В соответствии с методикой, предложенной в [2], следует рассмотреть четыре подзадачи: подсчет количества комбинаторных объектов (разбиений); получения из текущего объекта следующего в соответствии с введенным отношением порядка; получение по объекту его номера и обратная задача – из номера объекта генерировать сам объект. Дадим более формализованную постановку задачи.
Под разбиением n элементного множества A на k блоков понимается произвольное семейство ???(пи) = {В1, В2, …, Вk} такое, что ??? для 1≤i• S(n,k)=0 для k>n,
• S(n,n)=1 для n0. Считаем, что S(0,0)=1 – пустое семейство блоков есть разбиение пустого множества,
• S(n,0)=0 для n>0.
Основная формула, связанная с числами Стирлинга второго рода имеет вид: S(n,k)=S(n 1,k 1)+k*S(n 1,k), для 0Function GetQuan(n,k:Integer):Integer;
Var r:Integer;
Begin
If (k=1)Or (k=n) Then r:=1
Else Begin
r:=GetQuan(n 1,k 1);
If n>k Then r:=r+k*GetQuan(n 1,k);
End;
GetQuan:=r;
End;
Первая задача решена. Перейдем ко второй задаче. Для её решения требуется определить отношение порядка на множестве всех разбиений. Проблема не очевидная, однако, из рекуррентной зависимости для чисел Стирлинга второго рода следует простой рекурсивный способ получения всех разбиений. Для хранения разбиений определим глобальный массив: b:Array [1..NMax] Of Set Of 1..NMax), где NMax – некоторая константа.
Procedure GetAll (n, k: Integer);
Var i:Integer;
Begin
If n=1 Then < вывод разбиения>
Else Begin
If k>1 Then Begin
b[k]:=b[k]+[n]; {Размещаем элемент n в блок k.}
GetAll (n 1,k 1);
b[k]:=b[k] [n]; {Удаляем элемент n из блока k.}
End;
If (n>k) Then
For i:=1 To k Do Begin {Последовательное добавление элемента n в блоки, от 1 до k го.}
b[i]:=b[i]+[n]; {Добавляем элемент n в блок с номером i.}
GetAll (n 1,k);
b[i]:=b[i] [n]; {Удаляем элемент n из блока с номером i.}
End;
End;
End;
Исследуем структуру разбиений, например, пятиэлементного множества на три блока (табл. 3). Для этого получим результат для S(5,3), S(4,2), S(4,3) и можно для значения S(3,2), чтобы более наглядно просматривалась зависимость – табл. 3.
Таблица 3

В табл. 3 «жирным» шрифтом выделены те разбиения S(5,3), которые получаются из S(4,2) путем добавления третьего блока, состоящего из одного элемента, равного 5, а «жирным» курсивом показаны разбиения S(5,3), получаемые из разбиений S(4,3) добавлением пятого элемента к первому блоку. В следующих выделенных строках табл. 3 приводятся разбиения, получаемые добавлением пятого элемента ко второму и третьему блокам разбиений S(4,3).
Определим отношение порядка на множестве разбиений следующим, рекурсивным способом. Пусть есть два разбиения b1 и b2 множества из n элементов на k блоков. Считаем, что b1Из табл. 3 четко просматривается, какое разбиение является первым, а какое последним. Реализуем генерацию первого и последнего разбиений с помощью следующих процедур.
Procedure First (n, k: Integer);
Var i: Integer;
Begin
b[1]:=[1..(n k+1)];
For i:=2 To k Do b[i]:=[n k+i];
End;
Procedure Last(n,k:Integer); Var i:Integer;
Begin
For i:=1 To k 1 Do lst[i]:=[i];
lst[k]:=[k..n];
End;
Оформим проверку – является ли текущее разбиение, записанное в массиве b, последним при данных значениях n и k с помощью следующей функции.
Function IsLast (n, k: Integer):Boolean;
Var ret: Boolean;
i: Integer;
Begin
ret:=True;
For i:=1 To k 1 Do ret:=ret And (b[i]=[i]);
ret:=ret And (b[k]=[k..n]);
Islast:=ret;
End;
Для реализации логики требуется еще одна простая функция (GetIndex), определяющая номер блока, в котором принадлежит элемент m.
Function GetIndex (m: Integer): Integer;
Var i: Integer;
Begin
i:=1;
While Not(m In b[i]) Do Inc(i);
GetIndex:=i;
End;
Рекурсивный вариант логики генерации следующего разбиения имеет вид.
Procedure GetNext (n, k: Integer);
Var h,q: Integer;
Begin
h:=GetIndex(n); {h – номер блока, содержащего элемент n.}
b[h]:=b[h] [n]; {Исключение элемента n из блока h.)
If k>1 Then {Количество блоков больше одного.}
If (h=k) And (b[k]<>[]) Then Begin {Элемент n должен остаться в блоке h.}
If Not IsLast(n 1,k) Then {Это не последнее разбиение n 1 элемента на k блоков.}
GetNext(n 1,k);{Генерируем следующего разбиения n 1 элемента на k блоков.}
End
Else Begin
If h If IsLast(n 1,k) Then Begin {Это последнее разбиение n 1 элемента на k блоков?}
First(n 1,k); {Генерируем первое разбиение n 1 элемента на k блоков.}
h:=h mod k+1;{Если h = k, то h = 1, иначе h = h + 1.}
End
Else GetNext(n 1,q); {Генерируем следующее разбиение n 1 элемента на k блоков.}
b[h]:=b[h]+[n]; {Размещаем элемент n в блоке с номером h.}
End;
В этом случае схему генерации всех разбиений можно изменить. Напишем функцию сравнения двух разбиений.
Function Eq(q1,q2:Tmas):Boolean;{Имеются в виду следующие типы данных: Tset = Set Of 1..nn; TMas = Array[1..nn] Of TSet;}
Var i:Integer;
ret:Boolean;
Begin
ret:=True;
For i:=1 To k Do ret:=ret And (q1[i]=q2[i]);
Eq:=ret;
End;
Новый вариант процедуры GetAll.
Procedure GetAll;
Begin
First(n,k);
Last(n,k);
While Not Eq(a,lst) Do Begin
<вывод разбиения>;
GerNext(n,k);
End;
<вывод разбиения>;
End;
Перейдем к третьей задаче – определению по разбиению его номера (функция GetNum(n, k)). Если значение k равно единице, то и номер блока равен также единице, так как при любых разбиениях на один блок их количество равно одному. В противном случае определим номер блока (значение переменной h), к которому принадлежит элемент n. Если значение h равно значению k и блок состоит из одного элемента n, то мы находимся в первой части множества разбиений (элемент n находится в блоке с номером k и блок состоит из одного элемента) и имеем полное право записать GetNum = GetNum(n 1, k 1). При невыполнении условия, очевидно, что разбиение принадлежит ко второй части множества разбиений – из разбиений n 1 элемента на k блоков мы последовательно генерируем разбиения путем добавления n к существующим блокам. В этом случае требуется подсчитать количество разбиений n 1 элемента на k 1 блок (это число входит в наш номер GetQuan(n 1,k 1)), вычислить количество разбиений n 1 элемента по k блокам – это значение входить в номер h 1 раз, и, наконец, определить «остаток номера» – номер разбиения n 1 элемента на k блоков.
Function GetNum (n, k: Integer): Integer;
Var h: Integer;
Begin
If k=1 Then GetNum:=1
Else Begin
h:=GetIndex(n); {h – номер блока, содержащего элемент n.}
b[h]:=b[h] [n];
If (h=k) And(b[h]=[]) Then GetNum:=GetNum(n 1,k 1)
Else GetNum:= GetQuan(n 1,k 1)+(h 1)* GetQuan(n 1,k)+GetNum(n 1,k);
b[h]:=b[h]+[n];
End;
End;
Определение разбиения по его номеру является обратной задачей по отношению к рассмотренной выше. Пусть логика решения реализована в процедуре GetSet с входными параметрами: n – количество элементов в множестве, k– количество блоков, p – номер разбиения.. Найдем число s, равное S(n 1,k 1). Если p меньше или равно s, то искомое разбиение принадлежит первой части множества разбиений, когда элемент n в единственном числе находится в блоке k. Размещаем элемент в блоке и рекурсивно вызываем GetSet(n 1,k 1,p). Если значение p больше s, то разбиение принадлежит ко второй части множества разбиений, определяемой размещением n 1 элемента на k блоков и последовательным добавлением элемента n к каждому блоку. Исключим из p количество разбиений в первой части – p:=p s. Вычислим новое значение s, равное S(n 1,k) и найдем целое количество вхождений числа s в число p (h: = p Div s). Значение h показывает количество блоков, в которых «побывал» элемент n при разбиении n 1 элементного множества на k блоков. Причем, если остаток от деления p Mod s равен нулю, то элемент n все еще находится в блоке h, иначе он находится в следующем блоке (h+1). Размещаем элемент n в блоке с номером h, изменяем значение p (p: = p Mod s, а при p = 0, p: = s) и рекурсивно вызываем GetSet(n 1,k,p) с новыми параметрами.
Procedure GetSet (n, k, p: Integer);
Var s, h: Integer;
Begin
If n>0 Then Begin
s:=GetQuan(n 1,k 1);
If p<=s Then Begin
b[k]:=b[k]+[n]; {Элемент n помещаем в блок k.}
GetSet (n 1,k 1,p); {Генерация разбиения n 1 элемента на k 1 блок по номеру p.}
End
Else Begin{ p > s}
p:=p s;{Исключаем из номера ту часть, которая соответствует разбиениям на k блоков, причем последний блок состоит из одного элемента n.}
s:=GetQuan(n 1,k);
h:=p Div s; {Вычисляем номер блока для размещения элемента n.}
p:=p Mod s; {Определяем новое значение номера разбиения n 1 элемента на k блоков с учетом того, что элемент n размещен в требуемом блоке.}
If p=0 Then p:=s Else Inc(h); {Учитываем особенности операций Div и Mod.}
b[h]:=b[h]+[n]; {Элемент n размещаем в блоке с номером h.}
GetSet (n 1,k,p); {Рекурсивно по новому значению номера p генерируем разбиение n 1 элемента на k блоков.}
End;
End;
End;
 
1-1 можно быстро Скачать WoW аддоны бесплатно для всех классов очень классно! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40