Pull to refresh

Comments 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 и при этом количество всех разбиений удовлетворяет (по всей видимости ) формуле Эйлера (вероятно той самой из статьи в Вики), то все разбиения найдены.

Знаю, провалился, но попытаться должен был: )
3 1 1, так как + действие — разложение всего, что после 3 (наш х)
Два комментария:

  1. Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
    • Рассмотреть подмассив от первого до предпоследнего элемента; если он пуст (в исходном массиве — всего один элемент), заврешить работу.
    • Если же он не пуст, двигаться по подмассиву справа налево по равным элементам, остановившись на последнем из них «x» (движение справа налево по равным элементам мне кажется более естественным, чем поиск «первого минимального» при движении слева направо).

  2. Мне кажется «более естественной», опять же, генерация в обратном порядке — начиная с разложения N в одно слагаемое (равное N) — возможно, потому что именно это решение мне придумалось (я сейчас вспомнил, что когда-то решал эту задачу). Наглядно удобно представить это первое разложение как башню, составленную из поставленных в стопку N кубиков. Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево (справа от любой башенки стоит или башенка той же, или меньшей высоты).

    Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).

    «Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)


Поправки к №2 (конец дня, напутал лево / право в паре мест):

… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево слева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…

Далее, кубики из руки выставляем слева справа от этой укороченной башенки…

Да, спасибо, добавил. Про движение справа налево — может быть, спорить не буду. В принципе это уже можно рассматривать как оптимизацию алгоритма или как другой алгоритм.
Диаграмма Юнга, кстати, она как раз из кубиков, удобно действительно.

Мне сначала пришла такая ассоциация из жизни: несколько бочек (индекс) в ряд, в каждом по ведру (значение) воды.
Да-да, и мне физическая модель в голове помогает иногда понять математическую задачу, хотя я учился на математика (а стал программистом). С башнями из кубиков — я хотел обеспечить как можно более медленное опускание центра тяжести конструкции из самого высокого положения (для одной башенки из N кубиков) в самое низкое (для N башенок из одного кубика).
Кстати, хотел бы еще дополнить: вынос первого элемента из циклов при данном подходе имеет силу как для генерации разбиений, так и для генерации сочетаний, перестановок.
Т.е. в принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для других комбинаторных объектов.
А что будет после шага 3,1,1?
Вначале 3,2, а затем: нет больше единиц, как отработает алгоритм?
4,1 очевидно.
Находим наименьшее непоследнее число, — это 3, т.к. оно единственное непоследнее. Прибавляем к нему 1, а из последнего — вычитаем 1.
UFO just landed and posted this here
Вы считаете, что есть кто-то кто должен диктовать людям, о чем им думать, когда они идут по улице?
UFO just landed and posted this here
Кстати, реально почему Вы задумались об этой задаче? Какую задачу решали с помощью разбиений?
Никакую. Меня интересовали некоторое время проблемы научного творчества, а именно психология научного творчества. А тут вдруг комбинаторика подвернулась и очень кстати пришлась к некоторым моим философским (хотя, скорее, психологическим) соображениям.: )
В целом меня интересуют связи гуманитарных и не очень гуманитарных наук.
Ну и мой такой обобщающий вывод: особенно нет разницы во что играть: в шахматы ли, в комбинаторику, в построения каких-то абстракций. Эффект психологический при достижении результата примерно один и тот же.
Тут, конечно, можно спорить о сложности задач и проверять как сложность решенной задачи влияет на общий эффект… но это уже другой вопрос.
Ну не ходят люди по улице и не думают как разбить число на слагаемые от нечего делать.

С чего Вы это взяли? От нечего делать можно и не о таком задуматься. Вот мне как-то раз почитать в метро было нечего, так я стал в уме гауссинаду преобразовывать в полярные координаты. Не получилось, но время убил.
UFO just landed and posted this here
Я выше написал мотивы. Теперь, если не сложно, объясните, почему вы так беспокоитесь за чужое состояние мыслительного процесса.
UFO just landed and posted this here
Кстати в «гауссинаду преобразовывать в полярные координаты» я тоже не вижу смысла.

Я краем уха слышал, что в полярных координатах интеграл от неё берётся.
UFO just landed and posted this here
Интеграл между какими пределами? Ага. А неопределённый интеграл относится к т.наз. «неберущимся».
Отвечу одним предложением за автора: программистам задачи такого рода иногда задают на интервью.
UFO just landed and posted this here
Шаг 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)
  }
}
Спасибо. Интересно, но позвольте одно замечание, если бы вместо комментария написали хоть краткую заметку об оптимизации алгоритма, то пользы было бы больше… желательно с подробным объяснением.

Дело в том, что большинство комментаторов, включая автора, понимают, что в реализации есть лишние шаги.
Без попытки обидеть.
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 в массив единиц и приклеиваем его к концу исходного массива.
Sign up to leave a comment.

Articles