Computing the lexicographic indices of integer partition

Question

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that precedes it. How is the modification done when we restrict the maximum part and the number of partitions? I would like to use these indices in database search. It would be helpful even if we get a closed form formula when the number of parts is restricted to small number, for example $<15$ and the integer is $< 100$ with each part $<5$.

Answer 1

Lexicographic order seems more complex than reverse lexicographic order.
In reverse lex order, it becomes straightforward: define p(n,k) as the number of partitions of n with largest part k (alternatively with no more than k parts). It has the well known recursion p(n,k)=p(n,k-1)+p(n-k,k). Then, for any partition, say 5311, here with sum n=10, do
p(5+3+1+1,5 -1) = 23
p(3+1+1,3 -1) = 3
p(1+1,1 -1) = 0
p(1,1 -1) = 0
add them to get 26, and subtract that from p(5+3+1+1)= 42 to get the rank = 16. To see why this works, look at the transpose partitions counted by p(10,4), p(5,2) etc that are clipped of.

Answer 2

I'm not sure if the general answer is in this paper Algorithm 515: Generation of a Vector from the Lexicographical Index (as i havent read it, not available online), but it gives the algorithm for combinations, i.e from combination to index and index to combination.

In Knuth's The Art Of Computer Programming (TAOCP), Semi-numerical Algorithms also has examples and references of such algorithms (as mentioned in comment).

In general combinatorics this is called ranking and unranking (as mentioned in comment).

Given the fact that the items of a combinatorial sequence are lexicographicaly ordered and the fact that one can (efficiently) count the combinatorial items up to $N$.

The general algorithm to find the index of any combinatorial object in lexicographic order would be (rough outline):

1. For k in 0..n-1
2. Count how many items of length n-1-k have the kth element less than comb[k]
3. index is the sum of the counters.

In other words the most general algorithm for ranking (ordered) combinatorial objects (computing the index in the order given the combinatorial object), although not necessarily efficient, is:

Index = Compute how many come before given the order and the combinatorial object and add $1$

The associated (general) algorithm for unranking follows. Specificaly let $C(n)$ be the number of size-$n$ combinatorial objects of a certain type satisfying a recurrence relation of the form:

$$C(n) = u(n)C(n-1) + v(n)C(n-2) + w(n)C(n-3) + ..$$

where the coeficient $u(n)$, $v(n)$, $w(n)$, . . . are nonnegative. We call the objects corresponding to the term $u(n)C(n-1)$, objects of the first type, those corresponding to $v(n)C(n-2)$ objects of the second type, and so on. An algorithm for unranking can be given as follows:

Algorithm Unrank. Generate the $r$-th ($0 \ge r \lt C(n)$) combinatorial object.

1. Set $U = u(n)C(n-1)$, $V = v(n)C(n-2)$, $W = W(n)C(n-3)$, etc.
2. If $r<U$ then return the $r$-th object of the first type of size $n-1$ (recursion).
3. If $r<U+V$ then return the $(r-U)$-th object of the second type of size $n-2$ (recursion).
4. If $r<U+V+W$ then return the $(r-U-V)$-th object of the third type of size $n-3$ (recursion).
5. (And so on).

(reference: Generating Random Permutations, Jorg Arndt, PhD Thesis, pp 57)

Of course the previous algorithm is based on the fact that there is a lexicographic order and the counting of combinatorial items (e.g combinations, permutations, partitions etc..) is efficient (which is not always the case).

Especially note that partitions are easier to generate in reverse lexicographic order (i.e descending). A PhD thesis on encoding partitions as lexicographicaly ascending (instead of descending) and the reference FAST ALGORITHMS FOR GENERATING INTEGER PARTITIONS, ANTOINE ZOGHBIU and IVAN STOJMENOVIC, 1998

UPDATE: One can see partitions (along other combinatorial objects like eg permutations) as decision trees and then devise rank and unrank algorothms based on recursive decisions. More details in Decision Trees Ranking and Unranking, notes by Prof. Tesler

Answer 3

Maybe one possibility is to multiply each partition in lexicographic order by the number that represents its position in the sequence. Storing the partitions this way you retrieve the order by dividing the partition stored value by the original integer to partition. And you retrieve the correct partition terms by dividing them by the order. I dont know what the data model is, but of course somehow, together with the series of each "new transformed partition" you would also have to store the original value of the integer to partition, to compare with.