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

[whitefox]

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

спасибо, понял. количество переборов практически не меняется.

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

Но и это не предел. Можно ещё ускорить алгоритм если перечислять представления не в лексикографическом порядке, а в порядке некоторого кода Грея.

[upgrade]

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

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

так, снова задумался... почему если перебирать $p=m-n$ это эквивалентная задача?
расуждения:
когда из суммы вычитается количество слагаемых, убираем комбинацию единиц этой суммы (отсюда затем надо прибавть $1$)
но переборы то все равно делать все (минус один, который убрали), разве нет, не понимаю, откуда следует, что перебираются "только представления с известной суммой", если так, то и перебирать ничего не надо.

[aa_dav]

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

откуда следует, что перебираются "только представления с известной суммой"

Вы таки не поняли даже моего рекурсивного объяснения.
P.S.
В нём надо только еще добавить, для полной ясности, что для последней ячейки ничего перебирать уже не надо - её значение одно и сразу известно.

[upgrade]

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

Вы таки не поняли даже моего рекурсивного объяснения.

откуда у метода whitefox это следует. откуда это следует из рекурсивного перебора, мне понятно.

[aa_dav]

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

откуда у метода whitefox это следует

Его метод - это выкидывание из рекурсионного метода "всего лишнего". =)
Просто идёт концентрация на том что это своеобразный счётчик с динамической базой для цифр.

-- 05.06.2015, 14:04 --

P.S.
Ну и если вам понятно почему рекурсионный алгоритм перебирает только актуальные ряды, то остаётся только понять что метод whitefox генерирует точно такие же ряды. В конце концов всё крутится вокруг того как из текущее состояние ряда переходит в следующее.

[whitefox]

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

так, снова задумался... почему если перебирать $p=m-n$ это эквивалентная задача?

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

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

когда из суммы вычитается количество слагаемых, убираем комбинацию единиц этой суммы (отсюда затем надо прибавть $1$)
но переборы то все равно делать все (минус один, который убрали), разве нет

Число $m$-представлений равно числу $p$-представлений, так что никакие комбинации не убираются и никакие комбинации не добавляются.

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

откуда следует, что перебираются "только представления с известной суммой"

Пусть сумма элементов текущего представления $a$ равна $p$ и алгоритм преобразует его в представление $a'$ с суммой элементов $p'.$ Пусть $i$ будет индексом самого правого ненулевого элемента массива $a$ и пусть $i\ne1.$ Тогда алгоритм при $i\ne n$ изменит в массиве $a$ только три элемента:
$a'[i-1]=a[i-1]+1;$
$a'[i]=0;$
$a'[n]=a[i]-1;$
и при $i=n$ изменит только два элемента:
$a'[n-1]=a[n-1]+1;$
$a'[n]=a[n]-1.$
Из чего следует, что $p'=p.$

[svv]

whitefox
Когда я писал свой первый ответ в этой теме, мне очень хотелось уменьшить все $n$ элементов массива на единицу, а требуемую сумму — на $n$. Но я испугался, что будут сложности с объяснением. И... да.

[whitefox]

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

Но я испугался, что будут сложности с объяснением.

Зато сам алгоритм проще

[upgrade]

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

все $n$ элементов массива на единицу, а требуемую сумму — на $n$.

а если уменьшить на двойку, то сумму надо уменьшить на $2n$

[arseniiv]

А на двойку-то зачем уменьшать?

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

Но и это не предел. Можно ещё ускорить алгоритм если перечислять представления не в лексикографическом порядке, а в порядке некоторого кода Грея.

О, так что-то подобное возможно? Я подумал о коде Грея, но ничего не придумал (точнее, лень было попробовать выписать и посмотреть, что может получиться). Посоветуете литературу?

[svv]

В чём коварство математики. Двери, которые ведут из одной комнаты в другие, часто внешне мало чем отличаются друг от друга. Но войдя в эту дверь, Вы упростите ситуацию, войдя в другие — не упростите, или даже усложните. Можно также оставаться на месте и рассуждать, чем таким одна дверь принципиально отличаются от другой.

[ewert]

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

Можно ещё ускорить алгоритм если перечислять представления не в лексикографическом порядке, а в порядке некоторого кода Грея.

Ну сильно-то не ускоришь. Алгоритм и так линеен, причём на один шаг цикла приходится где-то операторов шесть в среднем.

[whitefox]

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

Посоветуете литературу?

Д.Кнут Искусство программирования т.4А.

-- 05 июн 2015, 20:22 --

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

Ну сильно-то не ускоришь. Алгоритм и так линеен, причём на один шаг цикла приходится где-то операторов шесть в среднем.

Вообще-то не линеен. В каждой итерации выполняется поиск крайнего справа ненулевого элемента, его сложность зависит от $n.$ А вот при использовании кода Грея действительно станет линейным.

[aa_dav]

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

Вообще-то не линеен. В каждой итерации выполняется поиск крайнего справа ненулевого элемента, его сложность зависит от $n.$

Есть ли способ избежать без кодов Грея?

[ewert]

А, ну я не вникал в Ваш алгоритм, просто попытался реализовать саму идею:

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

  n:=4;    { сумма                }
  k:=5;    { количество слагаемых }

  i:=k;
  while i>1 do begin
    if a[i]=0 then begin
        if i=2 then break;
        dec(a[i-1]);
        inc(a[i-2]);
        dec(i);
        if a[i]<>0 then begin
          a[k]:=a[i];
          a[i]:=0;
          i:=k;
          end;
        end
      else begin
        inc(a[i-1]);
        dec(a[i]);
        end;
    end;
 

Вышло вполне линейно и вполне так лексикографичненько:

  0  0  0  0  4
  0  0  0  1  3
  0  0  0  2  2
  0  0  0  3  1
  0  0  0  4  0
  0  0  1  0  3
  0  0  1  1  2
  0  0  1  2  1
  0  0  1  3  0
  0  0  2  0  2
  0  0  2  1  1
  0  0  2  2  0
  0  0  3  0  1
  0  0  3  1  0
  0  0  4  0  0
  0  1  0  0  3
  0  1  0  1  2
  0  1  0  2  1
  0  1  0  3  0
  0  1  1  0  2
  0  1  1  1  1
  0  1  1  2  0
  0  1  2  0  1
  0  1  2  1  0
  0  1  3  0  0
  0  2  0  0  2
  0  2  0  1  1
  0  2  0  2  0
  0  2  1  0  1
  0  2  1  1  0
  0  2  2  0  0
  0  3  0  0  1
  0  3  0  1  0
  0  3  1  0  0
  0  4  0  0  0
  1  0  0  0  3
  1  0  0  1  2
  1  0  0  2  1
  1  0  0  3  0
  1  0  1  0  2
  1  0  1  1  1
  1  0  1  2  0
  1  0  2  0  1
  1  0  2  1  0
  1  0  3  0  0
  1  1  0  0  2
  1  1  0  1  1
  1  1  0  2  0
  1  1  1  0  1
  1  1  1  1  0
  1  1  2  0  0
  1  2  0  0  1
  1  2  0  1  0
  1  2  1  0  0
  1  3  0  0  0
  2  0  0  0  2
  2  0  0  1  1
  2  0  0  2  0
  2  0  1  0  1
  2  0  1  1  0
  2  0  2  0  0
  2  1  0  0  1
  2  1  0  1  0
  2  1  1  0  0
  2  2  0  0  0
  3  0  0  0  1
  3  0  0  1  0
  3  0  1  0  0
  3  1  0  0  0
  4  0  0  0  0