В. Рубанцев - Как решать комбинаторные задачи на компьютере (1127108), страница 6
Текст из файла (страница 6)
Такая запись называется стандартной формой разбиения числа n наk слагаемых.В англоязычной литературе разбиения чисел называют Integer Partitions.61Если речь идет обо всех вариантах разбиения, то их число обозначают P(n).Мы легко найдём, чтоP(1)= 1> 1, потому что единицу невозможно представить иначе.P(2)= 2 > 2 11P(3)= 3 > 3 21 111P(4)= 5 > 4 31 22 211 1111P(5)= 7 > 5 41 32 311 221 2111 11111Эту процедуру можно продолжить и дальше, но уже сейчас явно прослеживается её рекурсивная сущность.
Однако мы начнём с итерационного алгоритма, описанного Витольдом Липским в книге [ЛВ88, Алгоритм 1.22]. Намнужно только перевести его на Си-шарп.Заданное число мы будем, как обычно, получать из компонента udNum иобозначим его буквой n. Все слагаемые мы поместим в массив adds, их общее число в текущем разбиении мы сохраним в поле nAdds, а числонайденных вариантов – в поле nVar. И для алгоритма Липского нам потребуется ещё один массив r, который показывает число повторов каждогослагаемого в разбиении. Например, для разбиения пятёрки 311 – тройкаповторяется 1 раз, а единица – дважды.//слагаемые:int[] adds;//число слагаемых:int nAdds = 0;//число повторов каждого слагаемого:int[] r;//число разбиений:int nVar = 0;Нажав на кнопку Все разбиения (Ит)!, мы по заданному числу n создаёмоба массива и переходим в метод part://РАЗБИВАЕМ ЧИСЛО ИТЕРАЦИОННОprivate void btnGenerate_Click(object sender, EventArgs e){int n = (int)udNum.Value;adds = new int[n + 1];r= new int[n + 1];string s = "Все разбиения числа " + n.ToString() + ": ";lstVar.Items.Add(s);part(n);s = "Всего " + nVar.ToString();lstVar.Items.Add(s);62lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}//Генерируем все разбиения числа n//и выводим в списокvoid part(int n){nVar = 0;//первое разбиение равно числу n:adds[1] = n;r[1] = 1;nAdds = 1;print(nAdds);//находим следующие разбиения:while (adds[1] > 1){int sum = 0;if (adds[nAdds] == 1){sum += r[nAdds];--nAdds;}sum += adds[nAdds];--r[nAdds];int l = adds[nAdds] - 1;if (r[nAdds] > 0) ++nAdds;adds[nAdds] = l;r[nAdds] = sum / l;l = sum % l;if (l != 0){++nAdds;adds[nAdds] = l;r[nAdds] = 1;}print(nAdds);}}Всякий раз, когда метод part сгенерирует новое разбиение, мы его печатаем на экране://ПЕЧАТАЕМ РАЗБИЕНИЕvoid print(int d){++nVar;string s = "";for (int i = 1; i <= d; ++i)for (int j = 1; j <= r[i]; ++j)63{s += (adds[i].ToString() + " ");}lstVar.Items.Add(s);//прокручиваем список вниз:lstVar.TopIndex = lstVar.Items.Count - 22;this.lstVar.Invalidate();Application.DoEvents();}И вот уже без особого напряжения мы получаем полный список разбиенийчисла 12 (Рис.
9.1).Рис. 9.1. Разбитое число 12Попробуем подойти к решению задачи с другого конца - с рекурсивного.Здесь нам на помощь спешит другой алгоритм [KS98, Algorithm 3.1], которыймы слегка заточим под наши нужды.64Чтобы не нагружать излишне нашу единственную кнопку, подселим к нейсоседку. Она вызывает другой метод и обходится без массива r://РАЗБИВАЕМ ЧИСЛО РЕКУРСИВНОprivate void btnGenRec_Click(object sender, EventArgs e){int n = (int)udNum.Value;adds = new int[n + 1];string s = "Все разбиения числа " + n.ToString() + ": ";lstVar.Items.Add(s);nVar = 0;RecPartition(n,n,0);s = "Всего " + nVar.ToString();lstVar.Items.Add(s);lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}А вот и рекурсивная разбивалка чисел:void RecPartition(int n, int B, int N){if (n == 0){nAdds = N;print(adds);}else{for (int i = 1; i <= Math.Min(B, n); ++i){adds[N + 1] = i;RecPartition(n - i, i, N + 1);}}}Заметьте, насколько сократился алгоритм! Добавляем метод печати очередного разбиения:void print(int[] a){++nVar;string s = "";for (int i = 1; i <= nAdds; ++i){int j = a[i];s += j.ToString();65if (i != nAdds) s += "+";}lstVar.Items.Add(s);//прокручиваем список вниз:lstVar.TopIndex = lstVar.Items.Count - 22;this.lstVar.Invalidate();Application.DoEvents();}Нажимаем кнопку Все разбиения (Рек)! – и вуаля, как говорят французы(Рис.
9.2).Рис. 9.2. Рекурсивная разбивалка в действии!Более того, рекурсивный алгоритм получился даже более универсальным,чем итерационный. Например, мы можем, иначе подготовив его вызов,сгенерировать не все разбиения, а только те, в которых наибольшее слагаемое не превышает заданного числа k.66Дополним интерфейс кнопкой btnK Все разбиения! и компонентом NumericUpDown. В методе btnK_Click обратите внимание на выделенные строчки://ГЕНЕРИРУЕМ ВСЕ РАЗБИЕНИЯ,//В КОТОРЫХ НАИБОЛЬШЕЕ СЛАГАЕМОЕ РАВНО kprivate void btnK_Click(object sender, EventArgs e){int n = (int)udNum.Value;adds = new int[n + 1];int k = (int)udK.Value;if (k > n){udK.Value=n;k = n;}string s = "Все разбиения числа " + n.ToString();lstVar.Items.Add(s);s= "k = " + k + ":";lstVar.Items.Add(s);nVar = 0;adds[1] = k;RecPartition(n-k, k, 1);s = "Всего " + nVar.ToString();lstVar.Items.Add(s);lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}Итак, перед вызовом нашего рекурсивного метода мы присваиваем первому слагаемому значение k, которое и остаётся неизменным во всех разбиениях, а все остальные слагаемые дополняют первое до числа n, но при этомне превышают k (Рис.
9.3).В нашем разменном примере эта ситуация может возникнуть при отсутствии «крупной» мелочи.Диаграммы ФеррерсаРазбиения чисел – для наглядности – принято изображать диаграммойФеррерса (Ferrers Diagram или Ferrers-Young Diagram). Для разбиения (1)она состоят из k строк, каждая из которых соответствует слагаемому вразбиении и состоит из последовательности точек, число которых равнозначению слагаемого.Например, для разбиения 8 = 4 + 3 + 1 можно построить такую диаграмму(Рис. 9.4).67Рис. 9.3. Разбиваем на меткие кусочки!Рис. 9.4. Разбиение числа 8Если перевернуть диаграмму Феррерса так, чтобы столбцы и строки поменялись местами (эта операция называется транспозицией), то мы получимсопряжённое разбиение заданного числа (Рис.
9.5).Рис. 9.5. Сопряжённое разбиение числа 868Легко видеть, что исходному разбиению соответствует сопряжённое 8 = 3+ 2 +2 + 1.Вы пока периферийно думайте над свойствами этих разбиений, а мы в этовремя научимся рисовать диаграммы Феррерса. Я не думаю, что онинастолько важны для нас, чтобы мы расщедрились на полноценную графику, так что мы будем просто ставить вместо кружочков буквы О.Подпишите под вызовом метода print ещё и новый метод printFerrers, который для каждого разбиения составит диаграмму Феррерса:void RecPartition(int n, int B, int N){if (n == 0){nAdds = N;print(adds);printFerrers(adds);}. .
.В методе printFerrers мы для каждого слагаемого создаём новую строкуиз букв О, взятых в количестве, равном очередному слагаемому a[i]://ПЕЧАТАЕМ ДИАГРАММУ ФЕРРЕРСАvoid printFerrers(int[] a){string s = "";for (int i = 1; i <= nAdds; ++i){s = new String('O', a[i]);lstVar.Items.Add(s);}lstVar.Items.Add("");//прокручиваем список вниз:lstVar.TopIndex = lstVar.Items.Count - 22;this.lstVar.Invalidate();Application.DoEvents();}И вот что у нас получилось (Рис. 9.6).69Рис. 9.6. Наше разбиение!Теперь давайте транспонируем диаграмму, а затем ещё раз подумаем, зачем нам это нужно.Поскольку задача чисто геометрическая, то мы справляемся с ней одниммахом:int nAdds2;int[] ConjPartition(int[] a){int[] b = new int[a.Length];int n = a.Length;nAdds2 = a[1];for (int i = 1; i < n; ++i)b[i] = 1;for (int j = 2; j <= nAdds; ++j)for (int i = 1; i <= a[j]; ++i)++b[i];70return b;}Обратите внимание: нам пришлось ввести новое поле nAdds2 для хранениячисла слагаемых в массиве b, что повлекло за собой правки в методахprintFerrers и RecPartition://ПЕЧАТАЕМ ДИАГРАММУ ФЕРРЕРСАvoid printFerrers(int[] a, int nPart){string s = "";for (int i = 1; i <= nPart; ++i).
. .void RecPartition(int n, int B, int N){if (n == 0){nAdds = N;print(adds);printFerrers(adds, nAdds);printFerrers(ConjPartition(adds), nAdds2);. . .Зато мы можем печатать не только «прямые» диаграммы Феррерса, но исопряжённые (Рис. 9.7).И вот пришла пора вернуться к нашему животрепещущему вопросу об этихдиаграммах. И по ним, и по методу ConjPartition мы видим, что количестворазбиений числа n на k частей в точности равно числу его разбиений, в которых наибольшая часть имеет значение k:nAdds2 = a[1];Число разбиений числа n на k частей обозначают P(n,k).Несколько полезных равенств:P(0,0) = 1P(n,0) = 0n>=1P(n,1) = P(n,n) = 1 n>=1Очевидно, что сумма всех возможных разбиений числа n на k частей равнаP(n), то естьP(n) = P(n,1) + P(n,2) + … + P(n,n)71Рис.
9.7. Оттранспонировались успешно!Ставим четвёртую - кнопку btnK2 Все разбиения на k!, - которая действуетподобно кнопке Все разбиения!, но вызывает рекурсивный метод RecPartition2://РАЗБИВАЕМ ЧИСЛО НА k ЧАСТЕЙprivate void btnK2_Click(object sender, EventArgs e){int n = (int)udNum.Value;adds = new int[n + 1];int k = (int)udK.Value;if (k > n){udK.Value = n;k = n;}string s = "Все разбиения числа " + n.ToString();lstVar.Items.Add(s);s = "на заданное число частей " + k + ":";lstVar.Items.Add(s);72nVar = 0;adds[1] = k;RecPartition2(n - k, k, 1);s = "Всего " + nVar.ToString();lstVar.Items.Add(s);lstVar.Items.Add("");lstVar.TopIndex = lstVar.Items.Count - 22;}Он, в свою очередь, почти близнец метода RecPartition, но печатает сопряжённое разбиение (Рис.
9.8), которое нам предоставляет метод ConjPartition:void RecPartition2(int n, int B, int N){if (n == 0){nAdds = N;print(ConjPartition(adds), nAdds2);}else{for (int i = 1; i <= Math.Min(B, n); ++i){adds[N + 1] = i;RecPartition2(n - i, i, N + 1);}}}И тут нам опять пришлось поправить уже готовый метод print, чтобы онумел работать с разными массивами, а не только с adds:void print(int[] a, int nPart){.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
