Создание массивов чисел с заданной суммой элментов

[upgrade]

arseniiv в сообщении #1024165 писал(а):

Вам так жутко надо параллелить получение комбинаций?

Ну вообще хотелось бы. Все таки массив длиной $20$ это совсем маленький массивчик.

[arseniiv]

Но ведь тут же дело не в том, какова длина одного массива, а какова длина всех массивов. При маленьком числе элементов, как будто, нет пользы от параллельности, а при большом есть вред из-за страшного использования памяти. Если только в серединке есть максимум — может, ну его?

[whitefox]

upgrade в сообщении #1024162 писал(а):

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

Алгоритм не считает комбинации у которых сумма не $5,$ а от любой комбинации у которой сумма $5$ сразу переходит к следующей в лексикографическом порядке комбинации с суммой $5.$

-- 06 июн 2015, 23:25 --

Кстати, предложенный алгоритм можно и распараллелить.

[ewert]

aa_dav в сообщении #1023955 писал(а):

Рекурсивный алгоритм "входит в стек" на величину $n$ максимум.

Не исключено. Однако не исключено и наоборот. Алгоритма-то предъявлено не было. Во всяком случае, не было предъявлено спецификации рекурсивной процедуры. Насчёт гаданий же -- я, конечно, экстрасенс, но не до такой степени.

[aa_dav]

ewert в сообщении #1024203 писал(а):

Алгоритма-то предъявлено не было.

А это что было:

Цитата:

Вот пусть у нас массив из $n$ элементов и заданная сумма $N$.
Рассматриваем какие значения может принимать 1-ая ячейка. Очевидно что от $1$ до $N-n+1$, т.к. если будет больше, то даже одни лишь единицы в последующих ячейках превысят сумму.
Значит делаем цикл по значениям в первой ячейке от 1 до $N-n+1$, а дальше в каждой итерации этого цикла сводим задачу к такой же на $n-1$ ячеек (остаток массива) и $N$ минус текущее значение в этой самой первой ячейке. Т.е. запускаем алгоритм на остаток массива просто с текущими лимитами и всё.

?

[ewert]

А что это было?...

Тут мало того, что нет ни одной рекурсии -- тут даже ни одной процедуры не специфицировано.

[ilya_msu]

whitefox в сообщении #1023552 писал(а):

Пусть массив имеет длину $n,$ и пусть заданное число равно $m,$ нужно перечислить все способы представления числа $m$ в виде суммы $n$ целых положительных чисел.

Необходимым условием разрешимости этой задачи является условие $m\geqslant n.$

Будем перечислять нужные представления в лексикографическом порядке. Для удобства перейдём к эквивалентной задаче — перечислить в лексикографическом порядке все представления числа $p=(m-n)$ в виде суммы $n$ целых неотрицательных чисел. Для обратного перехода к исходной задаче нужно будет каждый элемент найденного представления увеличить на 1.

Будем нумеровать элементы массива $a$ от $1$ до $n.$ Исходное состояние массива $a$ $[0,0,\dots,0,0,p],$ а заключительное $[p,0,0,\dots,0,0].$

1. присвоить массиву $a$ значение $[0,0,\dots,0,0,p];$
2. напечатать массив $a;$
3. выполнить $i:=n;$
4. пока $a[i]=0$ выполнять $i:=i-1;$
5. если $i=1,$ то завершить работу, иначе выполнить $t:=a[i]-1,\;a[i]:=0,\;i:=i-1;$
6. выполнить $a[i]:=a[i]+1,\;a[n]:=t;$
7. вернуться на шаг 2.

Огромное спасибо за помощь!

[whitefox]

ilya_msu, если время критично, то ewert показал как данный алгоритм сделать линейным:

1. присвоить массиву $a$ значение $[0,0,\dots,0,0,p];$
2. выполнить $i:=n;$
3. напечатать массив $a;$
4. если $i=1,$ то завершить работу;
5. выполнить $a[i]:=a[i]-1,\;a[i-1]:=a[i-1]+1;$
6. если $a[i]=0,$ то выполнить $i:=i-1$ и вернуться на шаг 3;
7. если $i=n,$ то вернуться на шаг 3;
8. выполнить $a[n]:=a[i],\;a[i]:=0,\;i:=n;$
9. вернуться на шаг 3.