2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 12:17 
Аватара пользователя
upgrade в сообщении #1023603 писал(а):
спасибо, понял. количество переборов практически не меняется.

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

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 12:29 
whitefox в сообщении #1023604 писал(а):
Количество переборов существенно меньше чем при полном переборе всех возможных комбинаций с последующей проверкой суммы элементов на равенство заданному числу, так как перечисляются только представления у которых сумма элементов уже равна заданному числу.

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 12:33 
upgrade в сообщении #1023607 писал(а):
откуда следует, что перебираются "только представления с известной суммой"


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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 12:55 
aa_dav в сообщении #1023608 писал(а):
Вы таки не поняли даже моего рекурсивного объяснения.

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 12:58 
upgrade в сообщении #1023613 писал(а):
откуда у метода whitefox это следует


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

-- 05.06.2015, 14:04 --

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 13:25 
Аватара пользователя
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.$

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 16:34 
Аватара пользователя
svv в сообщении #1023673 писал(а):
Но я испугался, что будут сложности с объяснением.

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 16:57 
svv в сообщении #1023673 писал(а):
все $n$ элементов массива на единицу, а требуемую сумму — на $n$.

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 17:11 
А на двойку-то зачем уменьшать?

whitefox в сообщении #1023604 писал(а):
Но и это не предел. Можно ещё ускорить алгоритм если перечислять представления не в лексикографическом порядке, а в порядке некоторого кода Грея.
О, так что-то подобное возможно? Я подумал о коде Грея, но ничего не придумал (точнее, лень было попробовать выписать и посмотреть, что может получиться). Посоветуете литературу?

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 17:12 
Аватара пользователя
В чём коварство математики. Двери, которые ведут из одной комнаты в другие, часто внешне мало чем отличаются друг от друга. Но войдя в эту дверь, Вы упростите ситуацию, войдя в другие — не упростите, или даже усложните. Можно также оставаться на месте и рассуждать, чем таким одна дверь принципиально отличаются от другой.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 19:49 
whitefox в сообщении #1023604 писал(а):
Можно ещё ускорить алгоритм если перечислять представления не в лексикографическом порядке, а в порядке некоторого кода Грея.

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 20:16 
Аватара пользователя
arseniiv в сообщении #1023682 писал(а):
Посоветуете литературу?

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

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

ewert в сообщении #1023730 писал(а):
Ну сильно-то не ускоришь. Алгоритм и так линеен, причём на один шаг цикла приходится где-то операторов шесть в среднем.

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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 20:25 
whitefox в сообщении #1023735 писал(а):
Вообще-то не линеен. В каждой итерации выполняется поиск крайнего справа ненулевого элемента, его сложность зависит от $n.$


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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 20:39 
А, ну я не вникал в Ваш алгоритм, просто попытался реализовать саму идею:

код: [ скачать ] [ спрятать ]
Используется синтаксис 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

 
 
 [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


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