Разложение числа на слагаемые

Данный онлайн калькулятор для введенного числа в диапазоне от 1 до 60 выводит все его представления в виде суммы положительных целых чисел, а также выводит количество таких представлений.

В математике представление числа в виде суммы положительных целых чисел называется разбиением натурального числа n, при этом в канонической записи разбиения слагаемые перечисляются в невозрастающем порядке. Описание алгоритма генерации всех разбиений можно найти под калькулятором.

Разбиение натурального числа

Натуральное число

Рассчитать

Число комбинаций

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

Задача разложения числа на слагаемые

В большинстве источников, которые можно легко найти поиском, приводится рекурсивный алгоритм разложения числа на слагаемые. В данном же калькуляторе, в силу технических причин, используется итеративный алгоритм. Логика алгоритма была взята из статьи на Хабре.

Так как логика алгоритма достаточно лаконичная, приведу ее целиком (с некоторыми комментариями):

Дано: исходный массив в виде единиц — А (1,1,1,1,1).

Размерность массива соответствует числу n, все разложения которого мы ищем.

0) Если получили сумму, тогда остановка алгоритма.

Как и автор статьи, я суммирую элементы в массиве, в конце должен остаться только один элемент с индексом 0, численно равный n.

1) Двигаясь по массиву слева направо, искать в массиве А первый минимальный элемент — x,
последний элемент не учитывается (не участвует в поиске минимального).

Нам нужно как значение элемента, так и его позиция в массиве. Поэтому я не пользуюсь встроенными в Javascript функциями типа min и findIndexOf, а использую одну итерацию по массиву, запоминая как текущий минимальный элемент, так и его позицию, а также сумму до текущего минимального элемента включительно (сумма понадобится ниже).

2) Перенести единицу из конца (последнего элемента) в найденный минимальный элемент x
(равносильно увеличению x на единицу и уменьшению на единицу последнего элемента).

Здесь прибавляется единица, и используется метод splice

3) Разложить сумму всех элементов после измененного элемента — x – на единицы.

Здесь добавляем единицы, используя ранее подсчитанную частичную сумму.

Код алгоритма на Javascript приведен ниже (разбиения выводятся в консоль):

function split(n) {
    var temp = [];
    for(var i = 0; i ＜ n; ++i) temp.push(1);
    while(temp[0] != n)
    {
        console.log(temp);
        var min = temp[0];
        var minindex = 0;
        var sum = temp[0];
        var tempsum = temp[0];
        for(var j = 1; j ＜ temp.length - 1; ++j) {
            tempsum += temp[j];
            if (min ＞ temp[j]) {
                min = temp[j];
                minindex = j;
                sum = tempsum;
            }
        }
        temp[minindex] += 1;
        sum += 1;
        temp.splice(minindex+1);
        for (var k = 0; k ＜ n - sum; ++k) temp.push(1);
    }
    console.log([n]);
}

Остается добавить, что, как и в любой другой комбинаторной задаче, число разбиений экспоненциально зависит от числа n. Если для 10 это 42, то для 50 это уже 204 226, а для 100 - 190 569 292. В данном калькуляторе установлено ограничение в 60, что дает 966 467 разложений и считается на моем ноутбуке примерно 12 секунд. При 100 у браузера заканчивалась память и он падал.

Зависимость числа разбиений от n является числовой последовательностью A000041 в онлайн энциклопедии целочисленных последовательностей и обладает рядом некоторых интересных свойств.