Алгоритм генерации всевозможных последовательностей

#алгоритм

Вот уже второй день ломаю голову над одной "типичной программерской" задачей. Суть
её заключается в том, что надо сгенирировать всевозможные числовые последовательности,
сумма всех членов которых должна равняться определенному числу. Я решил эту задачу
с помощью тупого перебора всевозможных последовательностей, но при больших числах время
выполнения оставляет желать лучшего. Какое бы вы предложили решение?

Скажем, дана последовательность от 1 до A, пользуясь которой нужно генерировать последовательности,
представляющие сумму числа N.
    

Ответы

Ответ 1

Рекомендую почитать учебники по теории чисел. Это называется композиции и разбиения
в зависимости от того считать ли 5=1+1+2+1+1 или 5=2+1+1+1+1 одним и тем же или нет.
В Википедии более менее доходчиво изложено.
Вот скажем пример алгоритма на Java:
http://www.btinternet.com/~se16/js/PartitionChoice.java
Два примера на C++:
http://www.cyberforum.ru/cpp-beginners/thread342773.html
http://www.cyberforum.ru/cpp-beginners/thread372700.html
Вот еще хорошая бумага:
http://www.tusur.ru/filearchive/reports-magazine/2008-1/113-119.pdf
Ну и конечно классика:
TAOCP том 4 
7.2.1.3. Generating all combinations
7.2.1.4. Generating all partitions


Ответ 2

например число 5, это 1+1+1+1+1, 2+3, 3+1+1...? правильно?
мой вариант:

5/1 = 5 - последний вариант проверки
5/5 = 1, те 5 раз по 1- первая последовательность
5/2 = 2, 2+2+1 - 2й вариант
5/3= 1+2 - 3й
 и тд. Лучше брать mod от числа и остачу делить дальше...

Надо еще додумать алгоритм.. но как то так...