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
morganschonbeckAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
pgloorConnect With a Mentor 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
    // 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.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 {
        partitionList.AddLast(answer);
        firstOp = true;
      }
    }
0
 
AgariciCommented:
this seems like homework....
and homework you should do by yourself

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


A.
0
 
Mike TomlinsonMiddle 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
 
morganschonbeckAuthor 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
 
morganschonbeckAuthor 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.

All Courses

From novice to tech pro — start learning today.