Todas las combinaciones posibles de X se dividen en N stacks

Question

Estoy seguro de que este problema tiene un nombre formal, y conocer ese nombre probablemente me ayude a encontrar la solución, pero no lo sé, y el problema para Google sigue señalando al Knapsack Problem, que no es lo mismo.

Quiero tomar algún valor X y encontrar todas las combinaciones posibles de dividir ese valor en N pilas de enteros enteros.

En caso de que mi redacción es confusa, aquí es un ejemplo de X = 4, N = 3

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

duplicación es aceptable, ya que es fácil de eliminar, pero lo ideal es que no sería calculado. Un algoritmo para resolver el problema sería perfecto, pero incluso descubrir que el problema tiene un nombre facilitaría la investigación. Gracias.

Answer 1

Esta es la respuesta de user434507 en 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; 
    } 
} 

Answer 2

Esto parece hacer el truco:

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; 
} 

Answer 3

Estos son, de hecho, como un integer partitions observaciones respuesta eliminados. Usando Mathematica:

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

Salida:

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

---

no pude encontrar una aplicación C#, pero aquí hay un par de preguntas relacionadas:

Elegant Python code for Integer Partitioning

Integer Partition in Java

Algorithm for generating integer partitions

---

Google golpea:

Integer Partition Algorithm by Jerome Kelleher

Integer Partition Algorithm by Daniel Scocco

Fast Algorithms for Generating Integer Partitions (PDF) (se ve pesado)

Stony Brook Algorithm Repository - Partitions