2014 dxdy logo

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

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




 
 MAPLE, разложение числа m на n различных слагаемых
Сообщение31.03.2015, 21:06 
Аватара пользователя
Доброго времени суток! Помогите разработать алгоритм и реализовать его в Maple.
Алгоритм должен генерировать кортежи(массивы) длиной не более $n$, сумма элементов которого равна $m$.
Хочу получить в и тоге матрицу такого вида (при $ m=3, n=4$):
$
\begin{bmatrix} 
    3 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 1 & 1 
\end{bmatrix}
$
продолжение
$
\begin{bmatrix} 
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 3 & 2 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 2 & 0 & 1 & 3 & 2 & 1 & 0\\ 0 & 0 & 1 & 0 & 2 & 1 & 0 & 1 & 2 & 3
\end{bmatrix}
$
Как видите, сумма элементов в столбце равна 3. Есть идеи?

 
 
 
 Re: MAPLE, разложение числа m на n различных слагаемых
Сообщение31.03.2015, 22:31 
Берете случайные компоненты от нуля до трех , проверяете равна ли сумма 3 и если не равна 3 то выбрасываете и генерите следующий

 
 
 
 Re: MAPLE, разложение числа m на n различных слагаемых
Сообщение01.04.2015, 01:37 
Аватара пользователя
mihailm в сообщении #998663 писал(а):
Берете случайные компоненты от нуля до трех , проверяете равна ли сумма 3 и если не равна 3 то выбрасываете и генерите следующий

А как понять, когда остановиться? И где гарантии, что все комбинации разбиения числа были представлены?

 
 
 
 Re: MAPLE, разложение числа m на n различных слагаемых
Сообщение01.04.2015, 03:38 
Если перебирать все возможные кортежи из $0..m^n$, то и гарантия есть, и лексикографический порядок, позволяющий перебрать их все без угадайки, пора ли заканчивать.

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

 
 
 
 Re: MAPLE, разложение числа m на n различных слагаемых
Сообщение01.04.2015, 09:19 
В математике это делается за одну строчку, поскольку есть соотв. команды. В мейпле тоже есть combinat[partition], но чуть не хватает параметров. Она умеет раскладывать число на положительные слагаемые. Возьмем число $m+n$, тогда partition(m+n,m+1) даст разбиения на положительные слагаемые с макс. величиной не больше $m+1$. Затем выбрать все векторы, длина которых равна $n$ (есть ли готовая команда?) и вычесть из всего векторы [1,...,1]. А потом для каждого полученного вектора взять все его различные перестановки. Опять же, имеется ли команда? В математике все это есть.

 
 
 
 Re: MAPLE, разложение числа m на n различных слагаемых
Сообщение01.04.2015, 09:45 
Аватара пользователя
Vince Diesel в сообщении #998790 писал(а):
В математике это делается за одну строчку, поскольку есть соотв. команды. В мейпле тоже есть combinat[partition], но чуть не хватает параметров. Она умеет раскладывать число на положительные слагаемые. Возьмем число $m+n$, тогда partition(m+n,m+1) даст разбиения на положительные слагаемые с макс. величиной не больше $m+1$. Затем выбрать все векторы, длина которых равна $n$ (есть ли готовая команда?) и вычесть из всего векторы [1,...,1]. А потом для каждого полученного вектора взять все его различные перестановки. Опять же, имеется ли команда? В математике все это есть.

Да, вот это решение мне очень нравится! Спасибо! Тему можно закрывать.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group