Conjugate Partitions
Description of the problem
An unordered \(k\)-partition of \(n\) is an ordered sequence of integers \(n_1 \leq \cdots \leq n_k\) such that \(n = \sum_{i=1}^k n_i\). We can picture such a partition as boxes stacked on top of each other:
When we read the diagram above we can view it as a \(3\)-partition of \(10\) as \(1\leq 4\leq 5\). But we can also read it as a \(5\)-partition of 10 as \(1\leq 2\leq 2 \leq 2\leq 3\). This is called the conjugate partition.
Today, I am going to describe a short recursive algorithm which calculates the conjugate partition of a given partition.
Algorithm
Given a \(k\)-partition of \(n\), the number of terms in the conjugate partition is given by the largest number in that partition. Then largest number in the conjugate partition is the length of the original partition. Once we observe that we can write our algorithm recursively
Algorithm Dual
Input: xs which is a k-partition n
Output: the conjugate partition of xs
Begin
If xs is null then
Return an empty list
Else
Let k be min(xs)
Let n be length(xs)
Let zs be the list containing k many n's
Let ys be the empty list
For each x in xs
If x > k then
Append x - k to ys
End
End
End
Return the list after appending Dual(ys) to zs
EndImplementation
Here is an implementation
(defun dual (xs &optional ys)
(if (null xs)
ys
(let ((k (car xs))
(n (length xs)))
(dual (remove-if #'zerop
(mapcar (lambda (x) (- x k))
xs))
(append (loop repeat k collect n) ys)))))
DUALLet us test it on the example whose picture I gave above:
(dual '(1 4 5))
(1 2 2 2 3)
(dual (dual '(1 4 5)))
(1 4 5)Now, let us test it on a large random partition:
(defvar xs (sort (loop repeat 20 collect (1+ (random 10))) #'<))
XS
xs
(1 1 1 2 2 2 3 4 5 5 5 7 8 8 9 9 9 9 9 9)
(dual xs)
(6 8 9 9 12 13 14 17 20)
(dual (dual xs))
(1 1 1 2 2 2 3 4 5 5 5 7 8 8 9 9 9 9 9 9)Efficiency Issues
Rainer Joswig
correctly commented
saying the original implementation wasn’t very efficient. Since then I
made few modifications making the implementation above even simpler. He
gave several different implementations, one of which is recursive.
Check out his versions here.