产生一个数的分区 [英] 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.

该算法应该返回所有可能的方法的一些可以是pssed作为正数小于或等于本身的总和的前$ P $。因此，例如对数 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?

编辑：问的题目是总和的数分解的，因为我真的不知道这是什么被调用。 <一href="http://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number#400810">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.

这是说，你可以做的比你的code越办越好。请参见这个，或其更新版本的 Python的算法，并通过大卫Eppstein的 的数据结构。

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屋！