Рассмотрим комбинаторную задачу о разбиении конечного множества объектов A={a1,a2, …,an} на циклы. Элементы a1,a2, …,at образуют цикл, at считается соседом a1 и a1,a2, …,ai, …,at= a2, …,ai, …,at, a1 = …= ai, …, at, a1, …,ai 1 = …= at, a1, …,ai 1, ai. При разбиении множества А на k циклов естественно считать, что никакие два из k циклов не имеют общих элементов. Количество способов разбиения элементов множества A на k циклов обозначим как s(n,k). Числа s(n,k) называют числами Стирлинга первого рода. Для них выполняются следующие равенства:
• s(n,k)=0 для k>n,
• s(n,0)=0 для n>0,
• s(n,n)=1 для n≥0,
• s(n,1)=1 для n>0.
Общая формула для вычисления чисел Стирлинга первого рода имеет вид: s(n+1,k)=s(n,k 1) + n*s(n,k), где 1
Введем понятие нормализованной формы записи разбиения. Пусть n=5 и k=3. Пример разбиения на три цикла: [4, 1, 5], [2], [3]. Это же разбиение имеет и другие формы записи: [5, 4, 1], [2], [3]; [1, 5, 4], [2], [3]. Нормализованной считаем последнюю запись. Еще пример – [1, 4], [2, 5], [3]. Другие формы записи: [1, 4], [5, 2], [3]; [4, 1], [2, 5], [3]; [4, 1], [5, 2], [3]. Нормализованной считаем первую запись. В нормализованной форме запись каждого цикла начинается с минимального числа, которое есть в цикле.
Определить схему генерации разбиений элементов множества на циклы, а значит и некое отношение порядка достаточно сложно. Воспользуемся следующим приемом. Поставим в соответствие каждой нормализованной записи разбиения некоторый код (числовое представление, которое строится однозначно по разбиению) так, что по коду однозначно восстанавливается разбиение. Введем отношение порядка на множестве кодов, будем генерировать коды в соответствии с этим отношением порядка, а из них получать соответствующие разбиения.
Правило формирования кода:
• Длина кода равна n.
• Элементу с минимальным значением в каждом цикле ставим в соответствие число ноль, как признак начала цикла, и записываем его в коде на место этого значения – если минимальное значение цикла равно 4, то ноль в коде записывается на четвертое место.
• Каждый цикл просматривается справа налево. Для каждого элемента цикла находится первый слева элемент, меньший его, и это значение записывается в коде на место, соответствующее рассматриваемому элементу цикла.
Пример. Пусть дано разбиение [1, 5, 4], [2], [3]. Три цикла, начальный вид кода 000**, записываем нулевые значения в позиции, соответствующие элементам, которые в нормализованной записи циклов являются первыми. Просматриваем справа налево единственный цикл, состоящий более чем из одного элемента. Берем 4, справа от элемента находится единственный элемент меньший его, это единица. Записываем в код единицу в четвертую позицию – 0001*. Берем 5, аналогичные действия приводят к коду 00011. Рассмотрим еще дано разбиение [1, 5], [2, 3], [4]. Начальное состояние кода 00*0*. После выполнения описанных действий он имеет вид 00201. Итак, структура кода (для нашего примера n=5, k=3): в первой позиции всегда записывается 0, во второй – 0 или 1, в третьей – 0, 1 или 2, в третьей – 0, 1, 2 или 3, и, наконец, в четвертой – 0, 1, 2, 3 или 4. Отметим, что в n позициях кода всегда записано k нулей. Обратное преобразование. Пусть дан код 00110. По расположению нулей однозначно можно записать [1, *, *,], [2], [5]. А затем, элементу 4 предшествует только 1 – [1, 4, *]. Место для 3 единственное, имеем разбиение [1, 4, 3], [2], [5]. Обратите внимание на то, что разбиению [1, 3, 4], [2], [5] соответствует другой код 00130. Все разбиения на циклы и их коды для примера n=5 и k=3 приведены в табл. 1.
Таблица 1
№
п/п Цикл Код №
п/п Цикл Код №
п/п Цикл Код
0 [1,5,4], [2], [3] 00011 12 [1,5,3], [2], [4] 00101 24 [1], [2,4,3], [5] 00220
1 [1,4], [2,5], [3] 00012 13 [1,3], [2,5], [4] 00102 25 [1], [2,3,4], [5] 00230
2 [1,4], [2], [3,5] 00013 14 [1,3,5], [2], [4] 00103 26 [1,5,2], [3], [4] 01001
3 [1,4,5], [2], [3] 00014 15 [1,3], [2], [4,5] 00104 27 [1,2,5], [3], [4] 01002
4 [1,5], [2,4], [3] 00021 16 [1,4,3], [2], [5] 00110 28 [1,2], [3,5], [4] 01003
5 [1], [2,5,4], [3] 00022 17 [1,3], [2,4], [5] 00120 29 [1,2], [3], [4,5] 01004
6 [1], [2,4], [3,5] 00023 18 [1,3,4], [2], [5] 00130 30 [1,4,2], [3], [5] 01010
7 [1], [2,4,5], [3] 00024 19 [1,5], [2,3], [4] 00201 31 [1,2,4], [3], [5] 01020
8 [1,5], [2], [3,4] 00031 20 [1], [2,5,3], [4] 00202 32 [1,2], [3,4], [5] 01030
9 [1], [2,5], [3,4] 00032 21 [1], [2,3,5], [4] 00203 33 [1,3,2], [4], [5] 01100
10 [1], [2], [3,5,4] 00033 22 [1], [2,3], [4,5] 00204 34 [1,2,3], [4], [5] 01200
11 [1], [2], [3,4,5] 00034 23 [1,4], [2,3], [5] 00210
Итак, мы генерируем коды, а из них при выводе, получаем соответствующее разбиение на циклы. Для этой цели требуется вспомогательная процедура формирования первого кода. Её вид:
Procedure First(t, k: Integer);
Var i: Integer;
Begin
For i:=t To t+k 1 Do a[i]:=0;
For i:=t+k To n Do a[i]:=1;
End;
В процедуре делается нечто большее. А именно, формируется не просто первый код, а первый код, начиная с позиции t, и коде содержится k нулей (циклов). Начальный вызов имеет вид First(1,k), а для рассматриваемого примера – First(1,3).
Для определения завершения процесса генерации разбиений необходимо хранить последний код.
Procedure Last; Var i:Integer;
Begin
For i:=1 To n Do lst[i]:=0;
For i:=2 To n k+1 Do lst[i]:=i 1; End; После этого можно сделать «набросок» общей процедуры генерации всех кодов:
Procedure Solve; Begin
First(1,k);
Last;
<формирование разбиения по коду и его вывод>;
While Not Eq(a,lst) Do Begin{Функция Eq предназначена для сравнения текущего (массив а) и последнего (массив lst) кодов.}
GetNext(n,0);
< формирование разбиения по коду и его вывод >;
End; End; При формировании разбиения по коду требуется «уметь» определять начало цикла, а затем находить элементы, принадлежащие циклу. Первая задача решается с помощью процедуры Print (код хранится в массиве a).
Procedure Print;
Var i:Integer;
Begin
For i:=1 To n Do
If a[i]=0 Then Begin {Определили начало цикла.}
Write(i); FindNext(i); Write(' ');{Выводим элементы, принадлежащие циклу.}
End;
WriteLn;
End;
Для решения второй задачи необходим просмотр массива a, начиная с элемента с номером n, и определение всех элементов, равных номеру найденной позиции. При этом нахождение элемента не говорит о завершении цикла – требуется найти элементы, указывающие на него, поэтому без рекурсивной реализации, логика не будет выглядеть так компактно – процедура FindNext. Проверьте работу процедур на следующих кодах: 00022 и 00024. В первом случае разбиение на циклы имеет вид [1], [2, 5, 4], [3], во втором случае – [1], [2, 4, 5], [3].
Procedure FindNext(t:Integer);
Var i:Integer;
Begin
For i:=n DownTo t Do
If a[i]=t Then Begin
Write(i);
FindNext(i);
End;
End;
Рассмотрим процедуру GetNext. Заметим, что просмотр кода начинается с последней позиции n, а параметрами процедуры являются m – номер позиции в коде (изменяется от n до 2, так как значение первого элемента никогда не изменяется и равно 0) и q – количество найденных при просмотре циклов. Первый вызов процедуры: GetNext(n,0);
Procedure GetNext(m,q:Integer);
Begin
If m>1 Then Begin {Значение первого элемента всегда равно 0.}
If a[m]=0 Then Inc(q); {Элемент является началом цикла?}
If (a[m]=0 )And (n m
Inc(a[m]);{Изменяем значение элемента с номером m.}
First(m+1,q);{Из «хвоста» кода – элементы с номерами m+1, …, n формируем первое разбиение.}
End;
End;
End;
Решение традиционной задачи [1] – определение по разбиению его номера в данном случае трактуется как получение номера по коду разбиения, ибо генерируются коды разбиений, а преобразовывать код в разбиение мы умеем. Данная специфика требует умения вычислять для каждого конкретного кода количество кодов меньшей размерности (меньшей длины и с меньшим количеством нулей). Определим массив count (count: Array[1..NMax, 1..NMax] Of Integer). Элемент count[t,q] равен количеству кодов, рассматриваемых с позиции t до позиции n, в которых есть q нулей и элемент в позиции i изменяется от 0 до i 1. Очевидно, что значения count[1,k] (при заданном значении n) равны числам Стирлинга первого рода s(n,k). Для чисел Стирлинга первого рода выполняется рекуррентное соотношение s(n,k)=s(n 1,k 1)+(n 1)*s(n 1,k). Оказывается, что и для введенных чисел (количества кодов) справедливо аналогичное соотношение: count[t,q] = count[t+1,q 1]+(t 1)* count[t+1,q]. Действительно, первое слагаемое дает «вклад» кодов, у которых в позиции t записан ноль, и с позиции t+1 подсчитываются все коды, содержащие q 1 ноль. Второе слагаемое определяет количество кодов, у которых в позиции t записано одно из возможных значений, а с позиции t+1 подсчитываются все коды, содержащие q нулей. Процедура формирования массива count имеет вид:
Procedure Prepare(n:Integer);
Var i,j:Integer;
Begin
For i:=1 To n+1 Do
For j:= 1 To n Do count[i,j]:=0;
count[n+1,0]:=1;
For i:=n DownTo 1 Do
For j:=0 To n i+1 Do
count[i,j]:=count[i+1,j 1]+(i 1)*count[i+1,j];
End;
Для рассматриваемого примера n=5 значения элементов count приведены в табл. 2.
Таблица 2
n k 1 0 1 2 3 4 5
1 0 0 24 50 35 10 1
2 0 24 50 35 10 1 0
3 0 24 26 9 1 0 0
4 0 12 7 1 0 0 0
5 0 4 1 0 0 0 0
6 0 1 0 0 0 0 0
После сделанных замечаний функция вычисления номера разбиения пишется следующим образом (первый вызов GetNum(n,0)):
Function GetNum (m, q: Integer):Integer;
Begin
If m=0 Then GetNum:=0 {При n равном нулю GetNum также равно нулю.}
Else
If a[m]=0 Then GetNum:=GetNum(m 1,q+1) {Элемент в позиции m является началом цикла. Номер разбиения n элементов на k циклов определяется номером разбиения, в котором последние n m+1 элементов образуют первое разбиение на q+1 цикл.}
Else GetNum:=Count[m+1,q 1]+(a[m] 1)*Count[m+1,q]+GetNum(m 1,q);{Последнее слагаемое дает «вклад» тех разбиений n элементов на k циклов, у которых последние n m+1 элементов образуют первое разбиение на q циклов.}
End;
Осталось рассмотреть последнюю задачу – дан номер разбиения, определить само разбиение, точнее код, ему соответствующий. Считаем, что входными параметрами нашей логики (процедура GetSet) являются m – номер позиции, q – количество циклов, num – номер разбиения. Первый вызов – GetSet(1,k,num) – с первой позиции, k циклов и данный номер num. Вычислим значение s, равное Count[m+1,q 1]. Если значение num меньше s, то искомое разбиение принадлежит множеству разбиений, с началом цикла в позиции m. В противном случае (num ≥ s) разбиение принадлежит множеству, для которого в позиции m не начинается цикл. Требуется убрать ненужные номера (num: = num – s), вычислить значение, записанное в позиции с номером m, откорректировать значение номера и перейти на генерацию разбиения со следующей, m+1 позиции. Для нахождения значения в позиции m необходимо взять из массива элемент Count[m+1,q] и подсчитать целое количество вхождений его в число num, а для определения нового значения num – остаток от числа этого вхождения. Новый номер определяет разбиение с позиции m+1, содержащее q циклов. Итак, реализация логики имеет вид:
Procedure GetSet(m, q, num:Integer);
Var s: Integer;
Begin
If m<=n Then Begin {Номер позиции должен быть меньше или равен n.}
s:=Count[m+1,q 1];
If num < s Then Begin
a[m]:=0; {Элемент в позиции с номером m является началом цикла.}
GetSet(m+1,q 1, num); {Генерируем «хвост» разбиения.}
End
Else Begin
num:= num s;{Изменяем значение номера – убираем количество номеров, соответствующих первой части рекуррентного соотношения.}
s:=Count[m+1,q];
a[m]:= num div s + 1; {Определение значения элемента в позиции m.}
num:= num mod s; {Делаем поправку значения num.}
GetSet(m+1,q, num); {Генерируем «хвост» разбиения.}
End;
End;
End;
