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

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

and homework you should do by yourself

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

A.

http://www.experts-exchange.com/Programming/Programming_Languages/C_Sharp/Q_21849655.html

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

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.

All Courses

From novice to tech pro — start learning today.

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

// TextBox textBox2 receives output

private LinkedList<string> partitionList = null;

private void button1_Click(object sender, EventArgs e) {

partitionList = new LinkedList<string>();

int n = Convert.ToInt32(textBox1.T

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 {

partitionList.AddLast(answ

firstOp = true;

}

}