Solved

Integer partitions

Posted on 2006-06-16
5
629 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
[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
  • Learn & ask questions
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 86

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

PeopleSoft Has Never Been Easier

PeopleSoft Adoption Made Smooth & Simple!

On-The-Job Training Is made Intuitive & Easy With WalkMe's On-Screen Guidance Tool.  Claim Your Free WalkMe Account Now

Question has a verified solution.

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

We all know that functional code is the leg that any good program stands on when it comes right down to it, however, if your program lacks a good user interface your product may not have the appeal needed to keep your customers happy. This issue can…
Introduction Hi all and welcome to my first article on Experts Exchange. A while ago, someone asked me if i could do some tutorials on object oriented programming. I decided to do them on C#. Now you may ask me, why's that? Well, one of the re…
In this video, viewers are given an introduction to using the Windows 10 Snipping Tool, how to quickly locate it when it's needed and also how make it always available with a single click of a mouse button, by pinning it to the Desktop Task Bar. Int…
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…

617 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