partition of integers [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question

A partition of a positive integer n is an non-increasing array of positive integers

a[1] , a[2] , ... , a[m]

satisfying

a[1] + a[2] + ... +a[m] = n.

m is called the length of this partition.

We can list all the partitions of n in an specified order. For example, if we use the rule by which a lexicography sorts all the English words, it's called the le开发者_开发技巧xicographic order. Another way, if we use the rule by which the C language compares strings, it's called the reverse lexicography order. And there is also a colex order.

1. To generate all the partitions of a integer n, we have a nice algorithm proposed by Stojmenovic, which has already been included in Knuth's book.

2. To generate all the partitions of n with length exactly m, we can use colex order,this algorithm is also included in Knuth's book.

3. To generate all the partitions of n with all their elements not exceeding k, we can use the algorithm in 1, just changing its initial condition and exit condition of the cycle.

Here comes my question: how to generate those partitions that have their length exactly be m, and their elements not exceeding k?

Here m and k are constants . Of course, a partition with its elements not exceeding k is equivalent to its first element not exceeding k.

---

Oh, I think I have solved it. for

a[1] + a[2] + ... + a[m] = n

can be written as

(k+1-a[1]) + (k+1-a[2]) + ... + (k+1-a[m]) = m(k+1)-n

and the latter one is just a reversed partition of m(k+1)-n !

---

How about recursion? To get every allowed partition of {n,m,k}, take a[1]=j for each j in [1,k] followed by every allowed partition of {n-j,m-1,j}.