Комментарии 32
3,2,2,1 -> 3,2,3. Или я не понял описание алгоритма?
В любом случае, к любому неочевидному алгоритму следует писать доказательство.
3 2 2 1, получаем за один проход 3 3 1 1
Вроде так лучше.
Дальше следовало бы расписать формальное доказательство корректности алгоритма.
А потом можно оценить его эффективность (хотя бы на минимальном уровне в виде O(N)) и прикинуть, нет ли явных проблем (ну, запись на php с его структурами данных, заточенными под совсем другие задачи, опустим). К примеру, поиск "места для вставки единицы" полным перебором массива выглядит избыточным (можно сразу держать ссылки на "ступеньки" в массиве длиной N), но, возможно, для чисел, для которых перебор разбиений делается на компе, это и несущественно.
На публикацию в реферируемом журнале imho слабовато (да и тема, как я понимаю, изучена ещё Эйлером), а курсовик бы вышел основательный.
Попытка № 1 доказательства корректности алгоритма
*разряд тут следует трактовать как индекс массива
Леммы
1) Каждое последующее разбиение уникально по составу, т.е. отличается хотя бы в одном разряде.
2) Каждое последующее разбиение хранит сумму заданного числа.
3) Члены каждого последующего разбиения выстроены по убыванию или равны между собой.
4) Работа алгоритма заканчивается тогда, когда первый разряд равен сумме числа.
Если в результате работы алгоритма выполнены условия 1,2,3,4 и при этом количество всех разбиений удовлетворяет (по всей видимости ) формуле Эйлера (вероятно той самой из статьи в Вики), то все разбиения найдены.
Знаю, провалился, но попытаться должен был: )
- Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
- Рассмотреть подмассив от первого до предпоследнего элемента; если он пуст (в исходном массиве — всего один элемент), заврешить работу.
- Если же он не пуст, двигаться по подмассиву справа налево по равным элементам, остановившись на последнем из них «x» (движение справа налево по равным элементам мне кажется более естественным, чем поиск «первого минимального» при движении слева направо).
- Мне кажется «более естественной», опять же, генерация в обратном порядке — начиная с разложения N в одно слагаемое (равное N) — возможно, потому что именно это решение мне придумалось (я сейчас вспомнил, что когда-то решал эту задачу). Наглядно удобно представить это первое разложение как башню, составленную из поставленных в стопку N кубиков. Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево (справа от любой башенки стоит или башенка той же, или меньшей высоты).
Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).
«Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)
… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию
Далее, кубики из руки выставляем
Диаграмма Юнга, кстати, она как раз из кубиков, удобно действительно.
Мне сначала пришла такая ассоциация из жизни: несколько бочек (индекс) в ряд, в каждом по ведру (значение) воды.
Т.е. в принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для других комбинаторных объектов.
Вначале 3,2, а затем: нет больше единиц, как отработает алгоритм?
В целом меня интересуют связи гуманитарных и не очень гуманитарных наук.
Тут, конечно, можно спорить о сложности задач и проверять как сложность решенной задачи влияет на общий эффект… но это уже другой вопрос.
Ну не ходят люди по улице и не думают как разбить число на слагаемые от нечего делать.
С чего Вы это взяли? От нечего делать можно и не о таком задуматься. Вот мне как-то раз почитать в метро было нечего, так я стал в уме гауссинаду преобразовывать в полярные координаты. Не получилось, но время убил.
Кстати в «гауссинаду преобразовывать в полярные координаты» я тоже не вижу смысла.
Я краем уха слышал, что в полярных координатах интеграл от неё берётся.
Ну и в коде несколько лишних операций. Вот мой вариант на 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)
}
}
Дело в том, что большинство комментаторов, включая автора, понимают, что в реализации есть лишние шаги.
Без попытки обидеть.
function 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 в массив единиц и приклеиваем его к концу исходного массива.
Нерекурсивный алгоритм генерации всех разбиений и композиций целого числа