Menu
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.
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:
So my question is: is there a more efficient algorithm for this?
EDIT: 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.
277
Theorem: k(n) is also the number of partitions of n into distinct, odd parts. We begin with the generating function P(x) = ∑p(n)xn which counts all partitions of all numbers n, with weight xn for a partition of n.
The number of partitions of n is given by the partition function p(n). So p(4) = 5. The notation λ ⊢ n means that λ is a partition of n. Partitions can be graphically visualized with Young diagrams or Ferrers diagrams.
In general, Bn is the number of partitions of a set of size n. A partition of a set S is defined as a family of nonempty, pairwise disjoint subsets of S whose union is S. For example, B3 = 5 because the 3-element set {a, b, c} can be partitioned in 5 distinct ways: { {a}, {b}, {c} }
Typically a partition is written as a sum, not explicitly as a multiset. Using the usual convention that an empty sum is 0, we say that p0=1. Example 3.3. 2 The partitions of 5 are 54+13+23+1+12+2+12+1+1+11+1+1+1+1.
It's called Partitions. [Also see Wikipedia: Partition (number theory).]
The number of partitions p(n) grows exponentially, so anything you do to generate all partitions will necessarily have to take exponential time.
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.
177
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
