生成数字的分区 [英] Generating the partitions of a number

问题描述

我需要一种算法来生成所有可能的正数分区，我想出了一个(作为答案发布)，但这是指数时间.

I needed an algorithm to generate all possible partitions of a positive number, and I came up with one (posted as an answer), but it's exponential time.

算法应该返回一个数可以表示为小于或等于其自身的正数之和的所有可能方式.因此，例如对于数字 5，结果将是:

The algorithm should return all the possible ways a number can be expressed as the sum of positive numbers less than or equal to itself. So for example for the number 5, the result would be:

• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1

所以我的问题是:有没有更有效的算法?

So my question is: is there a more efficient algorithm for this?

问题的标题是数字的总和分解"，因为我真的不知道这叫什么.ShreevatsaR 指出它们被称为分区"，所以我编辑了相应的问题标题.

Question was titled "Sum decomposition of a number", since I didn't really know what this was called. ShreevatsaR pointed out that they were called "partitions," so I edited the question title accordingly.

推荐答案

它叫做 分区.[另见维基百科:分区(数论).]

It's called Partitions. [Also see Wikipedia: Partition (number theory).]

分区的数量 p(n) 呈指数增长，因此您为生成所有分区所做的任何事情都必须花费指数时间.

The number of partitions p(n) grows exponentially, so anything you do to generate all partitions will necessarily have to take exponential time.

也就是说，你可以做得比你的代码做得更好.请参阅this，或Python 算法和数据结构 大卫·爱普斯坦.

That said, you can do better than what your code does. See this, or its updated version in Python Algorithms and Data Structures by David Eppstein.

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