Solved

Integer partitions

Posted on 2006-06-16
5
591 Views
Last Modified: 2012-06-27
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
0
Comment
Question by:morganschonbeck
5 Comments
 
LVL 11

Expert Comment

by:Agarici
ID: 16919511
this seems like homework....
and homework you should do by yourself

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


A.
0
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 16919908
See here for my "unoptimized, dumb, brute force solution"...
http://www.experts-exchange.com/Programming/Programming_Languages/C_Sharp/Q_21849655.html
0
 

Author Comment

by:morganschonbeck
ID: 16932108
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
 
LVL 5

Accepted Solution

by:
pgloor earned 500 total points
ID: 16933190
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
 

Author Comment

by:morganschonbeck
ID: 16934307
Thanks pgloor!!
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

This article introduced a TextBox that supports transparent background.   Introduction TextBox is the most widely used control component in GUI design. Most GUI controls do not support transparent background and more or less do not have the…
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
Access reports are powerful and flexible. Learn how to create a query and then a grouped report using the wizard. Modify the report design after the wizard is done to make it look better. There will be another video to explain how to put the final p…
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now