Given a natural number N, an ordered k-partition of N is a sequence \(a_1,\ldots,a_k\) of natural numbers such that \(N = a_1 + \cdots + a_k\). For the purposes of this note, we assume \(a_i\geq 0\). In this decomposition, we may assume that the sequence is ordered, that is, we are not allowed to alter the order of the terms \(a_i\). Then the partition is called an ordered k-partition of N. If we want a decomposition which is oblivious to the ordering of the numbers appearing in the decomposition of N, then the partition is called an unordered k-partition of N. In that case, we can assume without loss of generality that \(a_1\leq a_2\leq \cdots\leq a_k\).
In this note, I would like to describe a recursive algorithm which gives the ordered and unordered k-partitition of a natural number N together with the python code which implements the algorithm.
The case of ordered partitions is slightly easier that the unordered partition using recursion. Notice that if we have a k-partition of N of the form \[ N = a_1 + \cdots + a_k \] then we have a \((k-1)\)-partition of \(N - a_1\) \[ N - a_1 = a_2 + \cdots + a_k \] The smallest value for \(a_1\) is 1, and the largest value we can chose for \(a_1\) is such that \(N - a_1 = (k-1)\). Then means \(a_1\) can be at most \(N - k + 1\). Thus we can write our function
def OrdPart(N,k):
if N<0 or k<1 or N<k:
return([])
if N == k:
Ret = [ [ 1 for i in range(N) ] ]
elif k == 1:
Ret = [ [N] ]
elif k == 2:
Ret = [ [i,N-i] for i in range(1,N) ]
else:
Ret = []
for i in range(1,N-k+2):
for x in OrdPart(N-i,k-1):
Ret = Ret + [ [i] + x ]
return(Ret)A short note here: the range function in python starts
counting from 0. But if one starts at another number (say 1) it still
goes 1 short of the upper bound. One must increase the upper bound
number is such cases.
I don’t have to tell you that what we gain in clarity in writing the code recursively, we lose big time in computation time. Memoization is a good tool to cut down the computation time. I will a hash list (a dictionary in python lingo) whose keys were the parameters of the function call and whose value is the return value of the function. Here is the same function with memoization:
OrdPartStack = {}
def OrdPart(N,k):
if N<0 or k<1 or N<k:
return([])
if N == k:
Ret = [ [ 1 for i in range(N) ] ]
elif k == 1:
Ret = [ [N] ]
elif k == 2:
Ret = [ [i,N-i] for i in range(1,N) ]
else:
try:
Ret = OrdPartStack[(N,k)]
except:
Ret = []
for i in range(1,N-k+2):
for x in OrdPart(N-i,k-1):
Ret = Ret + [ [i] + x ]
OrdPartStack.update({(N,k):Ret})
return(Ret)I have a basic checking at the beginning to make sure that the arguments of the function are kosher. The special cases \(k=1\), \(k=2\) and \(N=k\) are needed for the recursion to terminate.
Let us see if the code works. I’ll start with the special cases
print OrdPart(7,1)
[[7]]
print OrdPart(9,9)
[[1, 1, 1, 1, 1, 1, 1, 1, 1]]
print OrdPart(5,2)
[[1, 4], [2, 3], [3, 2], [4, 1]]Now a small \(N\) with a small \(k\)
print OrdPart(6,4)
[[1, 1, 1, 3], [1, 1, 2, 2], [1, 1, 3, 1], [1, 2, 1, 2], [1, 2, 2,
1], [1, 3, 1, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1], [3, 1, 1,
1]]They return correctly. But try to look at the result of the following function call, it is not that easy to inspect the result one by one due to its length
A = OrdPart(8,6)
print(A)
[[1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 3, 1], [1, 1,
1, 2, 1, 2], [1, 1, 1, 2, 2, 1], [1, 1, 1, 3, 1, 1], [1, 1, 2, 1, 1,
2], [1, 1, 2, 1, 2, 1], [1, 1, 2, 2, 1, 1], [1, 1, 3, 1, 1, 1], [1, 2,
1, 1, 1, 2], [1, 2, 1, 1, 2, 1], [1, 2, 1, 2, 1, 1], [1, 2, 2, 1, 1,
1], [1, 3, 1, 1, 1, 1], [2, 1, 1, 1, 1, 2], [2, 1, 1, 1, 2, 1], [2, 1,
1, 2, 1, 1], [2, 1, 2, 1, 1, 1], [2, 2, 1, 1, 1, 1], [3, 1, 1, 1, 1,
1]]Instead, I’ll use
for x in A:
if len(x)!=6 and sum(x)!=8:
print "Error at ",xThe situation is more complicated with the unordered partitions but it is not too bad. Remember that we require \(N = a_1 + \cdots + a_k\) and \(a_1 \leq a_2 \leq \cdots \leq a_k\). So, if we re-write \[ N - a_1 = a_2 + \cdots + a_k \] this really does not give us a \((k-1)\)-partition of \(N - a_1\) because \(a_2\) must be greater than or equal to \(a_1\). Instead we write \[ (a_2 - a_1 + 1) + \cdots + (a_k - a_1 + 1) = N - a_ 1 - (k-1) (a_1-1) = N + k - 1 - k a_1 \] In other words, reducing the parameter \(k\) by 1 forces us to change \(N\) to \(N + k - 1 - k a_1\). Also, this equation also tells us the upper bound for \(a_1\): \[ N + k - 1 - k a_1 \geq k-1 \quad\Rightarrow\quad N \geq k a_1 \] Hence, the upper bound for \(a_1\) is \(\rfloor N/k\lfloor\).
So, let us write the code. I will write the implementation with memoization:
UnOrdPartStack = {}
def UnOrdPart(N,k):
if N<0 or k<0 or N<k:
return([])
if k == 1:
Ret = [ [N] ]
elif k == 2:
Ret = [ [i,N-i] for i in range(1,1+int(N/2)) ]
elif N == k:
Ret = [ [1 for i in range(N)] ]
else:
try:
Ret = UnOrdPartStack[(N,k)]
except:
Ret = []
for i in range(1,1+int(N/k)):
for x in UnOrdPart(N + k - 1 - k*i, k-1):
Ret = Ret + [ [i] + [(j+i-1) for j in x] ]
UnOrdPartStack.update({(N,k):Ret})
return(Ret)The recursion looks different from the previous case. The reason is that when we get the list of \((k-1)\)-partitions of \(N + k - 1 - k\cdot a_1\) we must shift each of the terms by \((a_1-1)\) to get an admissible partition. This is reflected in the code.
Let me test the code: the special case with an odd \(N\)
print UnOrdPart(5,2)
[[1, 4], [2, 3]]The special case with an even \(N\)
print UnOrdPart(8,2)
[[1, 7], [2, 6], [3, 5], [4, 4]]A smalll \(N\) and a small \(k\)
print UnOrdPart(9,4)
[[1, 1, 1, 6], [1, 1, 2, 5], [1, 1, 3, 4], [1, 2, 2, 4], [1, 2, 3,
3], [2, 2, 2, 3]]and a large \(N\) with a largish \(k\)
A = UnOrdPart(32,8)
for x in A:
if len(x)!=8 and sum(x)!=32:
print "Error at", xHere is the code in lisp with memoization which does the same thing.
(setq OrdPart-stack (make-hash-table :test #'equal))
(defun OrdPart-lookup (x) (gethash x OrdPart-stack))
(defun OrdPart-push (x y) (setf (gethash x OrdPart-stack) y))
(defun OrdPart (N k)
(cond ((or (< N 0) (< k 1) (< N k)) nil)
((= k 1) (list (list N))
((= k N) (list (loop for i from 1 to N collect 1)))
((= k 2) (loop for i from 1 to (1- N) collect (list i (- N i))))
(t (or (OrdPart-lookup (list N k))
(OrdPart-push (list N k)
(loop for i from 1 to (- (1+ N) k)
append (mapcar (lambda (x) (append (list i) x)) (OrdPart (- N i) (1- k)))))))))
(setq UnOrdPart-stack (make-hash-table :test #'equal))
(defun UnOrdPart-lookup (x) (gethash x UnOrdPart-stack))
(defun UnOrdPart-push (x y) (setf (gethash x UnOrdPart-stack) y))
(defun UnOrdPart (N k)
(cond ((or (< N 0) (< k 1) (< N k)) nil)
((= k 1) (list (list N))
((= k N) (list (loop for i from 1 to N collect 1)))
((= k 2) (loop for i from 1 to (floor (/ N 2)) collect (list i (- N i))))
(t (or (UnOrdPart-lookup (list N k))
(UnOrdPart-push (list N k)
(loop for i from 1 to (floor (/ N k))
append (mapcar (lambda (x) (append (list i) (mapcar (lambda (j) (+ i j -1)) x)))
(UnOrdPart (+ N (1- k) (* k i -1)) (1- k)))))))))