Solved

Integer partitions

Posted on 2006-06-16
5
597 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Najam
Having new technologies does not mean they will completely replace old components.  Recently I had to create WCF that will be called by VB6 component.  Here I will describe what steps one should follow while doing so, please feel free to post any qu…
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.
This Micro Tutorial will give you a basic overview how to record your screen with Microsoft Expression Encoder. This program is still free and open for the public to download. This will be demonstrated using Microsoft Expression Encoder 4.
Many functions in Excel can make decisions. The most simple of these is the IF function: it returns a value depending on whether a condition you describe is true or false. Once you get the hang of using the IF function, you will find it easier to us…

920 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

14 Experts available now in Live!

Get 1:1 Help Now