如何生成整数分区？(How do I generate integer partitions?)

我有一个像1,2,3号的列表，我想找到所有的组合模式，总结起来像5。例如一个特定的号码：

Sum=5
Numbers:1,2,3
Patterns:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

你允许就重复号码，因为他们没有在你的总和去。 哪种方式是最好的方案吗？

Answer 1:

这是改变决策问题的轻微的修改。 你应该能够找到大量的论文对这个问题，和动态编程解决方案，将采取不超过20行代码。

http://en.wikipedia.org/wiki/Change-making_problem

Answer 2:

这也可能帮助： 动态规划：组合和问题

Answer 3:

这些被称为数字的分区 ，你的问题似乎强加给它的数字你被允许在分区中使用的约束。

Answer 4:

这个问题被称为一个“双重限制整数分区”。 如果数字“允许”来概括至5是从一组V，那么它被称为“多重限制整数分区”。 有一个纸张通过里哈和James：“算法29：用于加倍和乘法限制分区有效算法”计算第16卷，1-2号，第163-168（1976）。 你应该阅读该文件并执行他们的算法。 了解如何做到这一点，您就可以实现独特的您的特定问题的优化。

Answer 5:

我会做递归最高数字第一次开始。 然后，在启动最高级别，每次走在许多层面数字。 只要累积的程度超过你的价值，下降到下一个号码。 如果仍然过大（或小），立即返回返回上一级和降低，要在未来数下来，然后在顶部再次开始下一个更深层次..

Answer 6:

    public static List<List<string>> Partition(int n, int max, string prefix)
    {

        if (n == 0)
        {
            _results.Add(prefix.Split(new char[] { ',' }).ToList());
        }

        for (int i = Math.Min(max, n); i >= 1; i--)
        {
            Partition(n - i, i, prefix + "," + i);
        }

        return _results;
    }

Answer 7:

您可以使用下面的代码..只要你想它wiil给你一个确切的答案..

void print(int n, int * a)

{
   int i ; 

   for (i = 0; i <= n; i++) 

   {

  printf("%d", a[i]); 

  }

 printf("\n"); 

}


void integerPartition(int n, int * a, int level)

{

   int first; 

  int i; 

  if (n < 1) 

 return ;    

 a[level] = n;

  print(level, a);

  first = (level == 0) ? 1 : a[level-1];

  for(i = first; i <= n / 2; i++)

   {

       a[level] = i; 

       integerPartition(n - i, a, level + 1);

   }

}

int main()

  {

   int n = 10;     

   int * a = (int * ) malloc(sizeof(int) * n); 

   integerPartition (n, a, 0); 

   return(0);

}

文章来源: How do I generate integer partitions?