Перечислить все разложения числа на слагаемые

[wrest]

Под разложением числа на слагаемые будем понимать как написано тут
https://ru.wikipedia.org/wiki/Композиция_числа

Цитата:

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

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

Всего для числа $n$ существует $2^{n-1}$ разложений на слагаемые.

Вопрос: как сгенерировать их все, ну или, пронумеровать их от $1$ до $2^{n-1}$ и по номеру сгенерировать соответствующее разложение.
Например берем число $5$ и его разложения:
Разложение $1$: $\{5\}$
Разложение $2$: $\{4,1\}$
Разложение $3$: $\{3,2\}$
...
Разложение $16$: $\{1,1,1,1,1\}$

Мне кажется, что можно как-то по нулям и единицам в двоичном представлении номера разложения, но не соображу как.

Из языков понимаю PARI/GP ну или просто описание алгоритма (или задам вопросы если будет непонятно).

[mihaild]

wrest в сообщении #1355729 писал(а):

Всего для числа $n$ существует $2^{n-1}$ разложений на слагаемые.

А как доказывается это утверждение, знаете? Из доказательства сразу видно как пронумеровать все композиции.
(ну или еще можно раскладывать рекурсивно, без всякой нумерации)

[arseniiv]

Дополню/проспойлерю предыдущее, раз уж написал. Метод пристального взгляда:

00000  5
00001  4 1
00010  3 1 1
00011  3 2
00100  2 1 2
00101  2 1 1 1
00110  2 2 1
00111  2 3
01000  1 1 3
01001  1 1 2 1
01010  1 1 1 1 1
01011  1 1 1 2
01100  1 2 2
01101  1 2 1 1
01110  1 3 1
01111  1 4

А если перечислять числа по-другому, может получиться более приличное для какого-то практического приложения перечисление композиций (по аналогии с применениями кодов Грэя, хотя сами коды Грэя вроде тут пользы не принесут). Однако тогда считать их по желанию будет дольше.

В перечислении в порядке 5, 4 1, 3 2, 3 1 1, 2 3, 2 2 1, 2 1 2, 2 1 1 1, 1 4, 1 3 1, 1 2 2, 1 2 1 1, 1 1 3, 1 1 2 1, 1 1 1 2, 1 1 1 1 1, наоборот, можно легко получать следующую композицию по предыдущей довольно прозрачным образом без необходимости хранить или вычислять её номер.

[wrest]

Мне надо для одной Ktina-загадки (про приписывание квадратов) научиться перебирать разложения, для чего надо научиться их генерировать...
arseniiv
Ваша зеленая нумерация очень удобная (меньше перебирать), но пристальный взгляд пока выявил только, что первым везде в двоичном представлении идет ноль, так что он, наверное, не нужен (т.к. бит надо в на уре $n-1$, т.е. для пятерки - четыре а не пять), а также видна закономерность с какого слагаемого начинается разложение.

-- 21.11.2018, 21:51 --

mihaild в сообщении #1355733 писал(а):

А как доказывается это утверждение, знаете?

Почитал в Вики, но там запутано и для общего случая (сколько разложений такой-то длины, потом складываем их все разных длин и получаем $2^{n-1}$)

[arseniiv]

В общем когда цифра меняется, мы начинаем новое слагаемое, а пока не меняется, добавляем к нему 1. Потому я поставил слева лишний ноль.

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

[mihaild]

Давайте возьмем $n$ шаров и попытаемся разложить их по $n$ корзинкам так, чтобы пустые корзинки остались в конце.
Встанем рядом с первой корзинкой и положим первый шар в нее (больше некуда). Теперь у нас на каждом шаге есть выбор: положить шар в текущую корзинку, или сделать шаг вперед и положить его в следующую (возвращаться назад бессмысленно - все шары одинаковые, можно было сразу положить сколько хотим), пропускать корзинки по условию нельзя.
Можно ли как-то красиво представить протокол наших действий в виде $n-1$-разрядного двоичного числа?

[wrest]

arseniiv
Ну например шестизначных квадратов что-то около 600, так что под них перед перебором можно просто сгенерировать все 32 разложения 6-терки на слагаемые.