2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 21:22 


05/09/16
5842
Под разложением числа на слагаемые будем понимать как написано тут
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 ну или просто описание алгоритма (или задам вопросы если будет непонятно).

 Профиль  
                  
 
 Re: Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 21:27 
Заслуженный участник
Аватара пользователя


16/07/14
3016
Москва
wrest в сообщении #1355729 писал(а):
Всего для числа $n$ существует $2^{n-1}$ разложений на слагаемые.
А как доказывается это утверждение, знаете? Из доказательства сразу видно как пронумеровать все композиции.
(ну или еще можно раскладывать рекурсивно, без всякой нумерации)

 Профиль  
                  
 
 Re: Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 21:32 
Заслуженный участник
Аватара пользователя


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

Код:
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, наоборот, можно легко получать следующую композицию по предыдущей довольно прозрачным образом без необходимости хранить или вычислять её номер.

 Профиль  
                  
 
 Re: Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 21:49 


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

-- 21.11.2018, 21:51 --

mihaild в сообщении #1355733 писал(а):
А как доказывается это утверждение, знаете?

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

 Профиль  
                  
 
 Re: Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 21:55 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 21:56 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Перечислить все разложения числа на слагаемые
Сообщение21.11.2018, 22:07 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group