# 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.

Morgan Scönbeck
###### Who is Participating?

Commented:
Below is my simple solution for the problem.

I'm not sure what exactly you want to do and I'm not sure I understand Integer Partitions since I got differnt resultas for your example.

In my example I added the resulting strings to a LinkedList of strings before I output the list to textBox2, line by line.

// TextBox textBox1 contains input

private void button1_Click(object sender, EventArgs e) {
int n = Convert.ToInt32(textBox1.Text);
partition(n, n, textBox1.Text + " = ", true);

// Output the resulting strings to TextBox textBox2
textBox2.Text = "";
foreach (string element in partitionList) {
textBox2.Text += element + Environment.NewLine;
}
}

private void partition(int n, int limit, string answer, bool firstOp) {
int i;
if (n > 0) {
for (i = Math.Min(n, limit); i > 0; i--) {
if (firstOp) {
partition(n - i, i, answer + i.ToString(), false);
} else {
partition(n - i, i, answer + " + " + i.ToString(), false);
}
}
} else {
firstOp = true;
}
}
0

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

A.
0

Middle School Assistant TeacherCommented:
See here for my "unoptimized, dumb, brute force solution"...
http://www.experts-exchange.com/Programming/Programming_Languages/C_Sharp/Q_21849655.html
0

Author Commented:
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
0

Author Commented:
Thanks pgloor!!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.