Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Integer partitions

Posted on 2006-06-16
Medium Priority
637 Views
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.

Morgan Scönbeck
0
Question by:morganschonbeck
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 11

Expert Comment

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

A.
0

LVL 86

Expert Comment

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

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

pgloor earned 2000 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

private void button1_Click(object sender, EventArgs e) {
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 {
firstOp = true;
}
}
0

Author Comment

ID: 16934307
Thanks pgloor!!
0

## Featured Post

Question has a verified solution.

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

This article describes a simple method to resize a control at runtime.  It includes ready-to-use source code and a complete sample demonstration application.  We'll also talk about C# Extension Methods. Introduction In one of my applications…
It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
This course is ideal for IT System Administrators working with VMware vSphere and its associated products in their company infrastructure. This course teaches you how to install and maintain this virtualization technology to store data, prevent vuln…
We’ve all felt that sense of false security before—locking down external access to a database or component and feeling like we’ve done all we need to do to secure company data. But that feeling is fleeting. Attacks these days can happen in many w…
###### Suggested Courses
Course of the Month7 days, 10 hours left to enroll