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

[whitefox]

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

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

Кнут о таком способе не пишет. А это почти стопроцентная гарантия, что другого способа просто нет.

Впрочем, алгоритм, реализованный в программе ewert, показывает, что для данной задачи лексикографический порядок тоже является неким кодом Грея.

[aa_dav]

А блин, да, возврат из рекурсии - тоже операция (и еще какая).
Так что да, я фигню спорол в предыдущем сообщении.

[ewert]

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

А блин, да, возврат из рекурсии - тоже операция (и еще какая).

Да маленькая. Там проблема в другом: если рекурсия на каждом шаге, то стек засоряется.

[aa_dav]

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

Да маленькая. Там проблема в другом: если рекурсия на каждом шаге, то стек засоряется.

Да млин что за мифология вокруг стека возникла вообще???
То у одного он не могёт, то у другого засоряется...
Оценки чем обоснованы?
По сабжевому алгоритму в чём они выражаются?

[ewert]

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

Да млин что за мифология вокруг стека возникла вообще???

Не мифология. Стек как класс требует для себя выделения памяти ваще; увы, это его характеристическое свойство.

И если для его хранения требуется память, хотя бы сопоставимая с памятью машины -- то это уже крайне нехорошо.

[aa_dav]

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

И если для его хранения требуется память, хотя бы сопоставимая с памятью машины -- то это уже крайне нехорошо.

Согласен - если автор топика перебирает массив из миллиона элементов, то нехорошо для стека совсем, да. Как и для перебора.

[ewert]

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

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

А эти две вещи меж собой, кстати, никак не связаны. Да и мульён -- не так уж и много (хоть это и не в тему)

[upgrade]

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

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

Чтобы понять суть. Это экспериментальное уменьшение на двойку. Можно увеличить на единицу. А можно попробовать умножить.
Пытаюсь понять что дает эта методика, уменьшение - еще одна операция.

[aa_dav]

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

Да и мульён -- не так уж и много (хоть это и не в тему)

Я не думаю что автора интересуют вырожденные случаи как и случаи перебор которых займёт больше миллиарда лет, так что стека тут за глаза.

[whitefox]

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

Пытаюсь понять что дает эта методика, уменьшение - еще одна операция.

Да никакая это не методика. Просто "внутренне представление" данных в алгоритме не обязано совпадать с "внешним представлением". Совершенно без разницы какими символами мы будем обозначать те или иные "цифры" внутреннего представления. Так в примере ewert для кодирования "слов" внутреннего представления использованы "цифры" $\{0,1,2,3,4\}.$ С равным успехом мог быть использован "алфавит" $\{a,b,c,d,e\},$ и, если Вам угодно, $\{1,2,3,4,5\}.$ Со всеми этими внутренними представлениями алгоритм будет работать одинаково, если только "цифры" алфавита линейно упорядочены.

[ewert]

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

Я не думаю что автора интересуют вырожденные случаи как и случаи перебор которых займёт больше миллиарда лет, так что стека тут за глаза.

Разбиение числа 25 на 15 слагаемых выдаёт 50 с чем-то миллионов комбинаций где-то за пару минут и создаёт файл в полтора гигабайта с лишком. Вот и прикиньте -- что выйдет, если загнать весь этот массив в стек, да ещё и со всеми локальными переменными.

[arseniiv]

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

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

Спасибо!

[aa_dav]

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

Вот и прикиньте -- что выйдет, если загнать весь этот массив в стек

А зачем его весь загонять в стек? =) Рекурсивный алгоритм "входит в стек" на величину $n$ максимум.

[upgrade]

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

Да никакая это не методика

Как то одним словом надо было назвать. Алгоритм видимо правильнее.

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

Просто "внутренне представление" данных в алгоритме не обязано совпадать с "внешним представлением".

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

-- 06.06.2015, 22:31 --

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

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

Каждая $n$ - это набор комбинаций, не вычислив комбинации для $n=4$ не получить комбинации для $n=5$.

[arseniiv]

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

Каждая $n$ - это набор комбинаций, не вычислив комбинации для $n=4$ не получить комбинации для $n=5$.

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