Solved

Integer partitions

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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Introduction This article series is supposed to shed some light on the use of IDisposable and objects that inherit from it. In essence, a more apt title for this article would be: using (IDisposable) {}. I’m just not sure how many people would ge…
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.
Nobody understands Phishing better than an anti-spam company. That’s why we are providing Phishing Awareness Training to our customers. According to a report by Verizon, only 3% of targeted users report malicious emails to management. With compan…

828 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