如何生成整数分区？ [英] How do I generate integer partitions?

问题描述

我有一个像1,2,3这样的数字列表，我想找到所有加起来等于5的特定数字的组合模式。例如：

I have a list of numbers like 1,2,3 and I want to find all the combination patterns that sum up to a particular number like 5. For example:

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

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

您可以重复输入不超过您总和的数字。

You're allowed to repeat numbers as far as they don't go over your sum. Which way would be best to program this?

推荐答案

这是对变更问题的略微修改。您应该能够找到很多有关此问题的论文，而动态编程解决方案最多需要20行代码。

This is a slight modification of the change making problem. You should be able to find plenty of papers on this problem, and a dynamic programming solution would take no more than 20 lines of code.

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

这篇关于如何生成整数分区？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！