asked on

Integer partitions

I'm looking for an algorithm (c#) to find all possible combinations of numbers with a certain sum.

For example:
X=7 (sum) and
n=3 (max nr of positions)

The algorithm should return :

6,1
5,2
4,3
5,1,1
4,2,1
3,2,2
3,3,1

These are called "integer partitions"
http://www.users.globalnet.co.uk/~perry/maths/partitionfunction/partitionfunction.htm
http://en.wikipedia.org/wiki/Integer_partition
http://mathworld.wolfram.com/Partition.html

The recursive formula might be the best way to list all the integer partitions.

Thanks for your help,
Morgan Scönbeck

Agarici

this seems like homework....
and homework you should do by yourself

however we can help you if you have any specific questions...

A.

Mike Tomlinson

See here for my "unoptimized, dumb, brute force solution"...
https://www.experts-exchange.com/questions/21849655/Math-algorithm-to-find-every-combination-of-an-unknown-amount-of-numbers-so-that-every-combination-will-equal-100.html

morganschonbeck

ASKER

It's not homework..

ok.. then I have a another question.

I need to store all my generated data in a array like this:

[0]
----[0]
-----[0]
-----[1]
----[1]
-----[0]
-----[1]
-----[2]
.....
[1]
.........

I know how many positions I need for the first level but I need to create the numbers of positions for the other two levels dynamic.
When I generate all the possible integer partitions for a given number it's based on the number I generate before..

My question: Can I use someting else than arrays for this? What is the best choice?

/Morgan

ASKER CERTIFIED SOLUTION

pgloor

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

morganschonbeck

ASKER

Thanks pgloor!!