Every possible combination of X split into N stacks

Question

I am sure this problem has a formal name, and knowing that name would probably help me find the solution, but I don't know it, and wording the problem for Google keeps pointing me to the Knapsack Problem, which isn't the same thing.

I want to take some value X and find every possible combination of splitting that value into N stacks of whole integers.

In case my wording is confusing, here is an example of X = 4, N = 3

Stack -> 1 | 2 | 3 |
----------------------
#1-----> 4 | 0 | 0 |
----------------------
#2-----> 3 | 1 | 0 |
----------------------
#3-----> 2 | 1 | 1 |
----------------------
#4-----> 2 | 2 | 0 |

Duplication is acceptable, since its easy to remove, but ideally it would not be calculated. An algorithm for solving the problem would be perfect, but even finding out of the problem has a name would make research easier. Thanks.

• Jodrell: So, you want n numbers that add to a exactly a sum of x? You don't want combinations/permutations of less than n parts to be included? Is zero a valid part. Does the order of parts matter? Would the same parts in a different order be a duplicate?
• Aasmund Eldhuset: Do you want just the number of combinations, or do you want to print all of the combinations?
• corn3lius: I think this may be similar to what you are looking for. stackoverflow.com/questions/2593781/…
• Jodrell: If you think again, this is in fact the NP Knapsack problem. Its just that your sack, I assume, has all the integers less than x and greater than 0 in it and, you only want combinations of n length.
• Kyeotic: @Jodrell Yes, n numbers that add to exactly x.

Answer 1

These are in fact integer partitions as a deleted answer remarks. Using Mathematica:

IntegerPartitions[4, 3] // PadRight //Grid

Output:

4 0 0
3 1 0
2 2 0
2 1 1

---

I could not find a C# implementation but here are a couple of related questions:

Elegant Python code for Integer Partitioning

Integer Partition in Java

Algorithm for generating integer partitions

---

Google hits:

Integer Partition Algorithm by Jerome Kelleher

Integer Partition Algorithm by Daniel Scocco

Fast Algorithms for Generating Integer Partitions (PDF) (looks heavy-duty)

Stony Brook Algorithm Repository - Partitions

• Kyeotic: @MrWizard Thank you for the name, that will help. I am interested in knowing how this is generated. The links don't seem to have any code in them that shows the algorithm being used.
• Kyeotic: @MrWizard, posted a second too soon, thank you for the code links!
• Mr.Wizard: @Tyrsius I'm adding more as I find them, keep watching.
• Kyeotic: That's perfect, as soon as I put together a c# method I will post it.
• Mr.Wizard: @Tyrsius I found one more link I wanted to include; it links to several different implementations and gives them ratings.

Answer 2

This seems to do the trick:

vector<vector<int> > partitions(int X, int N, int Y)
{
 vector<vector<int> > v;
 if(X<=1 || N==1)
 {
 if(X<=Y)
 {
 v.resize(1);
 v[0].push_back(X);
 }
 return v;
 }
 for(int y=min(X, Y); y>=1; y--)
 {
 vector<vector<int> > w = partitions(X-y, N-1, y);
 for(int i=0; i<w.size(); i++)
 {
 w[i].push_back(y);
 v.push_back(w[i]);
 }
 }
 return v;
 }
int main()
{
 vector<vector<int> > v = partitions(5, 3, 5);
 int i;
 for(i=0; i<v.size(); i++)
 {
 int x;
 for(x=0; x<v[i].size(); x++)
 printf("%d ", v[i][x]);
 printf("\n");
 }
 return 0;
}

• Kyeotic: I'm sure this is great, but I don't know what language its in, and I can't make sense of it all. Is a Vector a type of array? What does push_back do?
• Eugene Smith: It's C++ ... What language do you want your answer in?
• Alex Peck: It is C++ and vector is the STL implementation of a dynamic array.
• Kyeotic: C# if you can, but I am not above learning whats going on here.
• Eugene Smith: I don't know enough C# for that. Vector is just a dynamic array and push_back inserts an element in the end of the array. Function partitions(X, N, Y) returns the list of possible partitions of X into at most N stacks with no stack larger than Y.

Answer 3

This is user434507's answer in C#:

class Program
{
 static void Main(string[] args)
 {
 var v = Partitions(5, 3, 5);
 for (int i = 0; i < v.Count; i++)
 {
 for (int x = 0; x < v[i].Count; x++)
 Console.Write(v[i][x] + " "); 
 Console.WriteLine();
 }
 }
 static private List<List<int>> Partitions(int total, int stacks, int max)
 {
 List<List<int>> partitions = new List<List<int>>();
 if (total <= 1 || stacks == 1)
 {
 if (total <= max)
 {
 partitions.Add(new List<int>());
 partitions[0].Add(total);
 }
 return partitions;
 }
 for (int y = Math.Min(total, max); y >= 1; y--)
 {
 var w = Partitions(total - y, stacks - 1, y);
 for (int i = 0; i < w.Count; i++)
 {
 w[i].Add(y);
 partitions.Add(w[i]);
 }
 }
 return partitions;
 }
}

• Alex Peck: Updated with meaningful variable names