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

[ilya_msu]

Добрый вечер!
В процессе написания кода в матлабе для задачи возникла такая проблема -- есть массив целых чисел заданной длины, необходимо перебрать все варианты, в которых сумма элементов равна заданному числу.
То есть для массива из 3 чисел, с заданной суммой 5, необходимо вывести что-то типа этого
1 1 3
1 2 2
2 1 2
1 3 1
2 2 1
3 1 1

У меня был до этого кусок кода, который создавал числа заданной длины без 0 в заданной системе исчисления, поэтому я просто вставил его и для этой задачи. Получал результат, перебирая все варианты и проверяя условие на сумму:
1 1 1
1 1 2
1 1 3 +
1 2 1
1 2 2 +
1 3 2
...
Ясное дело, что перебирается огромное число лишних вариантов, на больших числах компьютер надолго задумывался, перебирая всю эту красоту.

Хотелось бы уменьшить время решения, перебирая только "нужные" варианты...

[arseniiv]

(Всё, что ниже — только если там нет встроенной функции, которая работала бы обычно быстрее, чем пользовательский код.)

Штука тут такая:

$f(n, s)$ — это все последовательности из $n$ чисел, каждое из которых принадлежит множеству $A\subset\mathbb N$, сумма которых равна $s$. Последовательности обозначаются квадратными, а множества — как обычно, фигурными скобками; $m..n \equiv \{ a : m\leqslant a\leqslant n, a\in\mathbb Z \}$.
$\begin{array}{lcl} f(0, s) & = & (s = 0) \mathbin? \{[]\} : \{\} \\ f(n\ne0, s) & = & \{ [a] + \ell : a\in A\cap0..s, \ell\in f(n - 1, s - a) \} \end{array}$

Конечно, простым переписыванием в виде рекурсивной функции реализовать не стоит. Это преобразуется как в алгоритм, последовательно выдающий комбинации, ходя вправо-влево по элементам последовательности, так и, если места не жалко, пишется динамическим программированием (находим все последовательности длин $0..n$ с суммами $0..s$ в правильном порядке; вроде, должно параллелиться хорошо).

-- Пт июн 05, 2015 00:34:06 --

(Наверно, какое-то из двух тут совершенно неуместно (второе?), но я чего-то не соображаю.)

[svv]

Обозначим элементы массива $a_k$, где $k=1..n$.
Нужно организовать $n-1$ вложенных циклов. Перенумеруем циклы, считая самый внешний первым, самый внутренний $(n-1)$-м.
Общее правило. В $k$-м цикле меняется $a_k$ от $1$ до $A_k$ (при фиксированных элементах с меньшими индексами).
Внутри $(n-1)$-м цикла известны все элементы, кроме $a_n$, тогда и он найдётся из известной суммы.
Ваша задача — вывести формулы для верхних пределов $A_k$ (они зависят от «состояния» внешних циклов).

[upgrade]

Можно считать поразрядно.
1 вычисляете все комбинации для суммы двух чисел меньше 5
2 сохраняете в файлике "2 разряда" (это будет 6 вроде пар)
3 выбираете из сохраненного и перебираете комбинации с 3-м числом на условие меньше равно 5
4 сохраняете в файлике "3 разряда"
...
Для сложных комбинаций до 50 разрядов реально, дальше увы.

[ewert]

Это -- задача о переборе всех $k$-элементных подмножеств из $n-2$ элементов, где $k+1$ -- количество чисел и $n-k+1$ -- их сумма.

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

[ilya_msu]

svv в сообщении #1023482 писал(а):

Обозначим элементы массива $a_k$, где $k=1..n$.
Нужно организовать $n-1$ вложенных циклов. Перенумеруем циклы, считая самый внешний первым, самый внутренний $(n-1)$-м.
Общее правило. В $k$-м цикле меняется $a_k$ от $1$ до $A_k$ (при фиксированных элементах с меньшими индексами).
Внутри $(n-1)$-м цикла известны все элементы, кроме $a_n$, тогда и он найдётся из известной суммы.
Ваша задача — вывести формулы для верхних пределов $A_k$ (они зависят от «состояния» внешних циклов).

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

[ewert]

Не вижу проблемы: ну пишем процедурку, в которой эн -- один из входных аргументов.

[svv]

Тогда ещё один внешний цикл по $n$ от $1$ до требуемой суммы.

[arseniiv]

(Оффтоп)

Можно ещё гиперплоскость представить соответствующую в $\mathbb Z^n$ (и обрезанный её кусок в виде внутренних точек какого-то симплекса). Сразу видно, что циклы спасут отца русской демократии перебор имеет какую-то логику (если её без этого не было видно при взгляде на лексикографически упорядоченные те точки ).

Например, редактируя пример ТС,

ilya_msu в сообщении #1023465, только в непоказательном порядке, писал(а):

1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1

Организовать перебор можно даже всего одним циклом while (намёк выше, получается, не удался), сделав функцию, строящую новую конфигурацию из текущей или возвращающей страшное значение, а также функцию, отступающую при этом на индекс назад с инициализацией следующих индексов заново. Фольклор! (Или по-другому факторизовать, я такие штуки давно не писал и мог посоветовать неудобный дизайн.)

[ilya_msu]

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

(Оффтоп)

Можно ещё гиперплоскость представить соответствующую в $\mathbb Z^n$ (и обрезанный её кусок в виде внутренних точек какого-то симплекса). Сразу видно, что циклы спасут отца русской демократии перебор имеет какую-то логику (если её без этого не было видно при взгляде на лексикографически упорядоченные те точки ).

Например, редактируя пример ТС,

ilya_msu в сообщении #1023465, только в непоказательном порядке, писал(а):

1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1

Организовать перебор можно даже всего одним циклом while (намёк выше, получается, не удался), сделав функцию, строящую новую конфигурацию из текущей или возвращающей страшное значение, а также функцию, отступающую при этом на индекс назад с инициализацией следующих индексов заново. Фольклор! (Или по-другому факторизовать, я такие штуки давно не писал и мог посоветовать неудобный дизайн.)

Мне, как в одной известной шутке, надо повторять два раза и медленно :) А без рекурсии никак не сделать, да?

[iifat]

Попробуйте найти Липский, Комбинаторика для программистов. Не помню уж, разобран ли там именно ваш пример, но, уверен, из неё вы узнаете множество полезных именно программисту приёмов.

[aa_dav]

ilya_msu в сообщении #1023535 писал(а):

А без рекурсии никак не сделать, да?

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

[Deggial]

Тема перемещена из форума «Околонаучный софт» в форум «Программирование»
Софт тут не при чём

[whitefox]

Пусть массив имеет длину $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.

[svv]

Реализация на C++ «переменного», неизвестного заранее количества вложенных циклов.
Эта функция формирует и печатает все троичные числа заданной разрядности n.
Предполагается, что достаточная память под массив a уже выделена.
k — номер разряда

Используется синтаксис C++

void f(int *a, int n)
{
   for (int k=0; k<n; ++k)
      a[k]=0;

   while (true)
   {
      Печать массива a
      int k;
      for (k=n-1; k>=0; --k)
      {
         ++a[k];
         if (a[k]<3) break;
         a[k]=0;
      }
      if (k==-1) break;
   }
}