Спасибо администрации Хабра за отзывчивость и молниеносную оперативность при восстановлении аккаунта!
Итак, плоды усилий долгих...
Нерекурсивный алгоритм генерации всех разбиений целого числа в лексикографическом
порядке, когда все элементы выстроены в порядке убывания, является альтернативным; в
Интернете представлено несколько способов порождения данных комбинаторных
объектов, однако, как это справедливо и относительно других комбинаторных алгоритмов,
реализации сводятся к двум типам — нерекурсивному и рекурсивному. Чаще можно встретить
реализации, которые не учитывают порядок вывода объектов или осуществляют
вывод по принципу дробления числа.
Приведенная ниже реализация работает по обратному принципу: исходное число изначально разбито на единицы, алгоритм работает до тех пор, пока число в нулевом индексе массива не станет равным сумме исходного числа. Особенностью данного алгоритма является то, что он крайне прост для понимания, однако это не лишает его некоторый специфики:
1) Первый объект просто выводится на экран в самом начале, таким образом, он вынесен за пределы циклов, фактически является инициализирующим;
2) Существует несколько способов реализации переноса единицы, которые могут, как упростить код, так и сделать его более запутанным;
3) Данная нерекурсивная реализация может служить наглядным примером для объяснения генерации комбинаторных объектов на нескольких процессорах, после незначительной модификации. Для разделения генерации на процессоры достаточно: а) определить элемент по его номеру и сделать инициализирующим; б) определить момент для остановки работы. Например, если известно число объектов генерируемых на одном процессоре, то достаточно ввести еще одну инкрементируемую переменную в верхний цикл и изменить условие выхода из самого верхнего цикла по достижении требуемого количества.
Код на языке PHP приведен только для демонстрации корректности алгоритма и может содержать лишние языковые средства, которые добавляют реализации избыточности.
Описание алгоритма
Дано: исходный массив в виде единиц — А (1,1,1,1,1).
Шаги
0) Если получили сумму (в случае реализации ниже, если нулевой индекс равен сумме числа), тогда остановка алгоритма.
1) Двигаясь по массиву слева направо, искать в массиве А первый минимальный элемент — x,
последний элемент не учитывается (не участвует в поиске минимального).
2) Перенести единицу из конца (последнего элемента) в найденный минимальный элемент x
(равносильно увеличению x на единицу и уменьшению на единицу последнего элемента).
4) Разложить сумму всех элементов после измененного элемента — x – на единицы.
Пример
А=(1,1,1,1,1)
2,1,1,1
2,2,1
3,1,1
<?php
$a = array(
1,
1,
1,
1,
1,
1,
1,
1,
1
);
print_r($a);
print '<br />';
$w = count($a);
$h = 0;
while ($a[0] != $w)
{
$min = $a[0];
$c = count($a) - 1;
$i = 0;
while ($i != count($a) - 1)
{
if ($a[$i] < $min)
{
$min = $a[$i];
$min2 = $i;
}
$i++;
}
if ($min2 == 0) $min2 = 0;
$a[$min2]+= 1;
$a[$c]-= 1;
if (in_array(0, $a)) array_pop($a);
array_splice($a, $min2 + 1);
foreach($a as $v)
{
$sum+= $v;
}
$j = 0;
$all = $w - $sum;
while ($j != $all)
{
$a[] = 1;
$j++;
}
print_r($a);
print '<br />';
unset ($all,$sum,$min,$min2);
$h++;
}
echo 'Amount: ' . ++$h;
?>
Update:
Операция с поиском и удалением 0 в массиве лишняя (так как используется array_splice, а затем новое заполнение массива), как правильно было замечено в комментарии участником dev26
Выводы
Хотел бы в конце поделиться одним наблюдением, я очень долго пытался понять, почему одни алгоритмы понятны сразу и легки для кодирования, а другие заставляют мучиться… и мучиться порой долго. Должен отметить, что этот алгоритм у меня получилось закодировать почти сразу, но только после того, как я получил однозначно понятное описание каждого шага. И тут есть важный момент, понять алгоритм и описать — задачи одна другой не легче. Однако, в алгоритмизации и составлении описания, особенно важным оказывается то, какими глаголами описываются действия в алгоритме — это (субъективно) в конечном счете может влиять и на конечную реализацию.
Литература
[1] Donald E. Knuth. The Art of Programming. Vol. 4. 2008.
[2] Dennis Ritchie and Brian Kernighan. The C Programming Language. 1978.
[3] Aleksandr Shen. Algorithms and Programming: Problems and Solutions.
[4] ru.wikipedia.org/wiki/Разбиение_числа
[5] en.wikipedia.org/wiki/De_Arte_Combinatoria
P.S. Несмотря на приведенный список литературы, алгоритм пришлось выводить заново.
Еще одно дополнение:
Вынос первого элемента из циклов при данном подходе имеет силу как для генерации разбиений, так и для генерации сочетаний, перестановок. В принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для генерации других комбинаторных объектов.
UPDATE
Алгоритм разбиений в соединении с алгоритмом перестановок позволяет генерировать и все композиции числа. Идея простая: для каждого разбиения вызывается функция генерации всех перестановок для этого разбиения.
<?php
set_time_limit(0);
//Функция генерации всех перестановок для разбиения
function perm($b) {
$b=array_reverse($b);
$a=array_reverse($b);
while (1) {
print_r($a);
print '<br/>';
if ($a ==$b) break;
$i=1;
while($a[$i] >= $a[$i-1]) {
$i++;
}
$j=0;
while($a[$j] <= $a[$i]) {
$j++;
}
$c=$a[$j];
$a[$j]=$a[$i];
$a[$i]=$c;
$c=$a;
$z=0;
for ($i-=1; $i > -1; $i--) $a[$z++]=$c[$i];
}
}
//Генерация всех композиций. Эта часть генерирует разбиения
//Заполнение массива
$g=0;
while ($g != 4){
$a[]=1;
$g++;
}
print_r($a);
print '<br>';
$w = count($a);
while ($a[0] != $w)
{
$min = $a[0];
$c = count($a) - 1;
$i = 0;
while ($i != count($a) - 1)
{
if ($a[$i] < $min)
{
$min = $a[$i];
$min2 = $i;
}
$i++;
}
if ($min2 == 0) $min2 = 0;
$a[$min2]+= 1;
$a[$c]-= 1;
array_splice($a, $min2 + 1);
$sum=array_sum($a);
for ($j=0; $j != $w-$sum; $j++) $a[] = 1;
perm ($a);
unset ($sum,$min,$min2);
}
?>
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Комментарии (32)
sashagil
01.06.2017 05:46Два комментария:
- Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
- Рассмотреть подмассив от первого до предпоследнего элемента; если он пуст (в исходном массиве — всего один элемент), заврешить работу.
- Если же он не пуст, двигаться по подмассиву справа налево по равным элементам, остановившись на последнем из них «x» (движение справа налево по равным элементам мне кажется более естественным, чем поиск «первого минимального» при движении слева направо).
- Мне кажется «более естественной», опять же, генерация в обратном порядке — начиная с разложения N в одно слагаемое (равное N) — возможно, потому что именно это решение мне придумалось (я сейчас вспомнил, что когда-то решал эту задачу). Наглядно удобно представить это первое разложение как башню, составленную из поставленных в стопку N кубиков. Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево (справа от любой башенки стоит или башенка той же, или меньшей высоты).
Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).
«Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)
sashagil
01.06.2017 06:28Поправки к №2 (конец дня, напутал лево / право в паре мест):
… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастаниюсправа на левослева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…
Далее, кубики из руки выставляемслевасправа от этой укороченной башенки…
dcc0
01.06.2017 07:10Да, спасибо, добавил. Про движение справа налево — может быть, спорить не буду. В принципе это уже можно рассматривать как оптимизацию алгоритма или как другой алгоритм.
Диаграмма Юнга, кстати, она как раз из кубиков, удобно действительно.
Мне сначала пришла такая ассоциация из жизни: несколько бочек (индекс) в ряд, в каждом по ведру (значение) воды.sashagil
01.06.2017 08:54Да-да, и мне физическая модель в голове помогает иногда понять математическую задачу, хотя я учился на математика (а стал программистом). С башнями из кубиков — я хотел обеспечить как можно более медленное опускание центра тяжести конструкции из самого высокого положения (для одной башенки из N кубиков) в самое низкое (для N башенок из одного кубика).
- Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
dcc0
01.06.2017 09:29Кстати, хотел бы еще дополнить: вынос первого элемента из циклов при данном подходе имеет силу как для генерации разбиений, так и для генерации сочетаний, перестановок.
Т.е. в принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для других комбинаторных объектов.
GospodinBaron
02.06.2017 00:58Меня возможно сейчас дико заминусуют. Но как в том анекдоте — плевать на день — год какой?
Хотелось бы спросить, а зачем и кому это нужно?
Ну не ходят люди по улице и не думают как разбить число на слагаемые от нечего делать.
Можно было бы хотя бы в одном предложении написать мотивацию сего действа?
P.S. Нет. Ссылки не помогли.dcc0
02.06.2017 01:18Вы считаете, что есть кто-то кто должен диктовать людям, о чем им думать, когда они идут по улице?
GospodinBaron
02.06.2017 09:43Вы по моему ушли в какую-то странную область. Мне сложно следовать вашей логики.
Zenitchik
02.06.2017 13:22Кстати, реально почему Вы задумались об этой задаче? Какую задачу решали с помощью разбиений?
dcc0
02.06.2017 14:09Никакую. Меня интересовали некоторое время проблемы научного творчества, а именно психология научного творчества. А тут вдруг комбинаторика подвернулась и очень кстати пришлась к некоторым моим философским (хотя, скорее, психологическим) соображениям.: )
В целом меня интересуют связи гуманитарных и не очень гуманитарных наук.
dcc0
02.06.2017 14:19Ну и мой такой обобщающий вывод: особенно нет разницы во что играть: в шахматы ли, в комбинаторику, в построения каких-то абстракций. Эффект психологический при достижении результата примерно один и тот же.
Тут, конечно, можно спорить о сложности задач и проверять как сложность решенной задачи влияет на общий эффект… но это уже другой вопрос.
Zenitchik
02.06.2017 13:27Ну не ходят люди по улице и не думают как разбить число на слагаемые от нечего делать.
С чего Вы это взяли? От нечего делать можно и не о таком задуматься. Вот мне как-то раз почитать в метро было нечего, так я стал в уме гауссинаду преобразовывать в полярные координаты. Не получилось, но время убил.GospodinBaron
03.06.2017 09:41Вы не поняли. Фраза имеет абстрактный смысл. Речь не о улице и не о том, о чем человек думает идя по ней.
Речь о том почему вообще человек думает о решении какой-то задачи, в которой на первый взгляд нет смысла.
Поскольку я лично этот смысл не увидел, то и решил спросить какой смысл увидел автор.
Кстати в «гауссинаду преобразовывать в полярные координаты» я тоже не вижу смысла.
Особенно если понимать физический смысл кривой Гаусса. Получилось у Вас или нет — не столь важно.
Но что-то Вас заставило об этом подумать.
Вы же не ехали в метро и не думали как бы тут залить все краской. Вы думали о функции.
P.S. Я исхожу и наивной предпосылки, что человек он разумный… Но я могу и ошибаться.dcc0
03.06.2017 12:01Я выше написал мотивы. Теперь, если не сложно, объясните, почему вы так беспокоитесь за чужое состояние мыслительного процесса.
GospodinBaron
03.06.2017 18:09У Вас действительно странная реакция.
У меня очень простая логика. Если человек публикует статью, то он расчитывает, что это интересует не только его одного. Тем более статья была без введения с пустого места. Это значит этим занимаются многие и объяснять не нужно, либо я лично чего-то не знаю и не понимаю.
Пройдя по ссылкам я не нашел объяснения, поэтому задал вопрос о теме. Вот и все.
Меня совершенно не интересует Ваша персона. По крайней мере я не вижу повода.
Меня обычно интересует то что я не понимаю. Вот и все.
Теперь все стало на свои места. Вопросов больше не имею. За Вами следить не собираюсь.
Zenitchik
03.06.2017 12:44Кстати в «гауссинаду преобразовывать в полярные координаты» я тоже не вижу смысла.
Я краем уха слышал, что в полярных координатах интеграл от неё берётся.GospodinBaron
03.06.2017 18:13Интеграл от нее вроде бы равен 1 по определению. Все остальное легко посчитать.
В наше время знание аналитического решения не так сильно помогает в жизни.
Да и потом в жизни больше нужно знать попадаем мы в 3сигма или нет.Zenitchik
04.06.2017 00:08Интеграл между какими пределами? Ага. А неопределённый интеграл относится к т.наз. «неберущимся».
sashagil
02.06.2017 20:35Отвечу одним предложением за автора: программистам задачи такого рода иногда задают на интервью.
GospodinBaron
03.06.2017 10:03+1. Хороший ответ! Принимается! Вот такое предложение в начале статьи можно было бы написать и это сняло бы многие вопросы.
dev26
02.06.2017 14:09Шаг 3 — лишний (ноль может появиться только на последнем месте и он не влияет на сумму).
Ну и в коде несколько лишних операций. Вот мой вариант на JavaScript, хоть он местами и тяжело читается ;)
function part(n) { let a = new Array(n).fill(1) console.log(a) while(a[0] != n) { // step 0 let m = a.slice(0, -1).reduce((m,n,i)=>(a[m]>n ? i:m), 0) // step 1 ++a[m]; --a[a.length-1] // step 2 a = a.concat(new Array(a.splice(m+1).reduce((s,n)=>s+n, 0)).fill(1)) // step 4 console.log(a) } }dcc0
02.06.2017 14:11Спасибо. Интересно, но позвольте одно замечание, если бы вместо комментария написали хоть краткую заметку об оптимизации алгоритма, то пользы было бы больше… желательно с подробным объяснением.
Дело в том, что большинство комментаторов, включая автора, понимают, что в реализации есть лишние шаги.
Без попытки обидеть.
Zenitchik
02.06.2017 16:28function partI(n) { let a = new Array(n).fill(1); console.log(a) while(a.length>1) { let sum = a.pop(), i = a.length -1; while(i>0 && a[i-1]==a[i]){ sum += a.pop(); --i; } a[i]+=1; sum-=1; a = a.concat(new Array(sum).fill(1)); console.log(a); } }
В случае JavaScript так лучше.
1. Выталкиваем последний элемент массива в переменную sum;
2. Выталкиваем из массива элементы один за другим и прибавляем их к sum до тех пор, пока они равны друг другу, последний из них (равных друг другу элементов) — не выталкиваем, он — искомый.
3. Искомый элемент увеличиваем на единицу, а переменную sum — уменьшаем на единицу.
4. Раскладываем значение sum в массив единиц и приклеиваем его к концу исходного массива.
aamonster
3,2,2,1 -> 3,2,3. Или я не понял описание алгоритма?
В любом случае, к любому неочевидному алгоритму следует писать доказательство.
dcc0
Отлично, дополню алгоритм одним словом: первый минимальный (если двигаться слева направо). Внимание: последний не учитывается.
3 2 2 1, получаем за один проход 3 3 1 1
aamonster
Вроде так лучше.
Дальше следовало бы расписать формальное доказательство корректности алгоритма.
А потом можно оценить его эффективность (хотя бы на минимальном уровне в виде O(N)) и прикинуть, нет ли явных проблем (ну, запись на php с его структурами данных, заточенными под совсем другие задачи, опустим). К примеру, поиск "места для вставки единицы" полным перебором массива выглядит избыточным (можно сразу держать ссылки на "ступеньки" в массиве длиной N), но, возможно, для чисел, для которых перебор разбиений делается на компе, это и несущественно.
На публикацию в реферируемом журнале imho слабовато (да и тема, как я понимаю, изучена ещё Эйлером), а курсовик бы вышел основательный.
dcc0
Спасибо за отзыв, в общем-то я так сначала и подумал, что для журнала не потянет. С доказательством сложнее, но попробую, правда, на словах, без формул.
dcc0
И, как говорят математики, то что алгоритм удовлетворяет всем условиям — «это легко видеть»: )
dcc0
Нет, с настоящим доказательством, скорее всего ничего не выйдет. Только попытка:
Попытка № 1 доказательства корректности алгоритма
*разряд тут следует трактовать как индекс массива
Леммы
1) Каждое последующее разбиение уникально по составу, т.е. отличается хотя бы в одном разряде.
2) Каждое последующее разбиение хранит сумму заданного числа.
3) Члены каждого последующего разбиения выстроены по убыванию или равны между собой.
4) Работа алгоритма заканчивается тогда, когда первый разряд равен сумме числа.
Если в результате работы алгоритма выполнены условия 1,2,3,4 и при этом количество всех разбиений удовлетворяет (по всей видимости ) формуле Эйлера (вероятно той самой из статьи в Вики), то все разбиения найдены.
Знаю, провалился, но попытаться должен был: )