8

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.

Kyeotic
  • 19,697
  • 10
  • 71
  • 128
  • 1
    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? – Jodrell Jun 13 '12 at 16:53
  • Do you want just the number of combinations, or do you want to print all of the combinations? – Aasmund Eldhuset Jun 13 '12 at 16:59
  • 2
    I think this may be similar to what you are looking for. http://stackoverflow.com/questions/2593781/print-all-ways-to-sum-n-integers-so-that-they-total-a-given-sum – corn3lius Jun 13 '12 at 17:03
  • 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. – Jodrell Jun 13 '12 at 17:03
  • @Jodrell Yes, `n` numbers that add to exactly `x`. – Kyeotic Jun 13 '12 at 17:12
  • @AasmundEldhuset Print of all the combinations. – Kyeotic Jun 13 '12 at 17:12
  • Look for Partition Functions http://www.wolframalpha.com/input/?i=partition+function+q&lk=1&a=ClashPrefs_*MathWorld.PartitionFunctionq- – corn3lius Jun 13 '12 at 17:14
  • @Jodrell, Perhaps you are right. I may be misunderstanding the Knapsack problem, but I thought it was with items having two values (weight and cost), and so I didn't go to in-depth. I will read more on it now. – Kyeotic Jun 13 '12 at 17:15
  • Take a look at this [question](http://stackoverflow.com/questions/4146632/algorithm-to-generate-all-unique-permutations-of-fixed-length-integer-partitions) – Andrei Jun 13 '12 at 17:16
  • This is "integer partition into k parts" http://en.wikipedia.org/wiki/Partition_(number_theory) – MBo Jun 13 '12 at 17:25

3 Answers3

5

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

Community
  • 1
  • 1
Mr.Wizard
  • 24,179
  • 5
  • 44
  • 125
  • @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 Jun 13 '12 at 17:50
  • @MrWizard, posted a second too soon, thank you for the code links! – Kyeotic Jun 13 '12 at 17:53
  • 1
    @Tyrsius I'm adding more as I find them, keep watching. – Mr.Wizard Jun 13 '12 at 17:53
  • That's perfect, as soon as I put together a c# method I will post it. – Kyeotic Jun 13 '12 at 17:59
  • @Tyrsius I found one more link I wanted to include; it links to several different implementations and gives them ratings. – Mr.Wizard Jun 13 '12 at 18:01
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;
}
Eugene Smith
  • 9,126
  • 6
  • 36
  • 40
  • 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? – Kyeotic Jun 13 '12 at 17:41
  • It's C++ ... What language do you want your answer in? – Eugene Smith Jun 13 '12 at 17:44
  • It is C++ and vector is the STL implementation of a dynamic array. – Alex Peck Jun 13 '12 at 17:45
  • C# if you can, but I am not above learning whats going on here. – Kyeotic Jun 13 '12 at 17:45
  • 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. – Eugene Smith Jun 13 '12 at 17:47
1

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
  • 4,603
  • 1
  • 33
  • 37