This site is supported by donations to The OEIS Foundation.

Ranking and unranking functions

From OeisWiki
(Redirected from Catalan ranking and unranking functions)
Jump to: navigation, search

This article page is a stub, please help by expanding it.



The following definitions are from Kreher & Stinson[1]:

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. Thus, ranking and unranking can be considered as inverse operations.

Here are slightly more formal mathematical descriptions of these concepts. Suppose that is a finite set and . A ranking function will be a bijection

.

A rank function defines a total ordering on the elements of , by the obvious rule

.

Conversely, there is a unique rank function associated with any total ordering defined on .

If rank is a ranking function defined on , then there is a unique unranking function associated with the function rank. This function unrank is also a bijection,

.

unrank is the inverse function of the function rank, i.e., we have

,

for all and all .

For a shorter formal definition, see[2]

Local rank vs. Global rank

Above definitions presuppose that there is a only finitely many combinatorial objects (or structures) in the set . This is true when we consider, for example, the object's position in the finite subset of objects of the same size. This is what the author (AK) of this page calls a Local rank. However, if we are interested about the combinatorial object's position among the whole infinite ensemble of the said combinatorial structures (which includes all sizes), then we have to, (for example), add the partial sum of counts of smaller objects to the local rank, to get what the author of this page calls a Global rank. Formally, we have:

where gives the size of the combinatiorial structure and gives the number of similar combinatorial structures of size .

Similarly, the Global unranking function can be computed with the help of Local unranking function as:

where has been computed with the help of auxiliary function as

thus , for will result a monotone (i.e. non-decreasing) integer sequence where each non-negative integer occurs times in succession:

.

Note that the above definition of contains the argument explicitly in its parameter list, in contrast to the definition of unrank as given by Kreher & Stinson where the result is implicitly assumed to depend on it.

Now we see that a global ranking function is a bijection from the whole enumerable set of the said combinatorial structures to nonnegative integers  :

and conversely, a global unranking function is its inverse (i.e. ), a bijection from non-negative integers to the combinatorial structures in question:

.

Sometimes, any pair of such functions, of which the other function is a bijection between the enumerable set and nonnegative integers, and the other its inverse, are called (global) ranking and unranking functions for the combinatorial structures in question, even if they would not respect any order based on conspicuous criteria, like e.g. lexicographic ordering or any of its variants or even a size-wise ordering of the elements in . See for example Alternative Catalan Orderings.

Ranking and unranking functions for specific combinatorial structures

In general, it's always possible to use the above scheme for constructing ranking and unranking functions for any enumerable combinatorial structure which has at least one parameter (usually the structure's "size", e.g. a number of vertices, edges, elements, etc.) that grows without limit from zero (or one) onward, but which nevertheless gets only finite number of times any particular finite value. However, in some cases shortcuts are possible.

Ranking and unranking functions for Catalan objects

When ranking and unranking (i.e. generating) Catalan objects, it's fortunate that many combinatorial interpretations of Catalan numbers allow an easy and unambiguous encoding as nonnegative integers, thus the set in above definitions will actually be a subset of , and functions like for those interpretations can be represented as integer sequences. The most obvious integer encoding for many Catalan interpretations uses totally balanced binary sequences, which consists of following binary strings

{{10}, {1010, 1100}, {101010, 101100, 110010, 110100, 111000}, {10101010, 10101100, 10110010, 10110100, 10111000, 11001010, 11001100, 11010010, 11010100, 11011000, 11100010, 11100100, 11101000, 11110000}, ...}

where in the th subsequence there are A000108() binary sequences, each of length .

In this case, the (local) unranking function is given by the array A213704, and considered as a dyadic function A213704bi(size,lrank) it gives the th such balanced binary string of bits, converted to decimal.

The auxiliary function is in this case a function that returns the smallest integer such that , where means the nth Catalan number, A000108(n), that is, the smallest integer for which A014137(k) .

This gives us the sequence A072643, where each occurs times:

{0, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, ...}

Now, setting means that the global unranking function can be obtained with a function Gunrank(i) = A213704bi(A072643(i),(i - A014137(A072643(i)-1))). This function has been submitted as the sequence A014486 into OEIS.

For ranking totally balanced binary sequences, one uses the local ranking function A080301 and the global ranking ranking function A080300 (or A215406).


The implementations of Catalan ranking and unranking functions in various programming languages can be found at separate source code for Catalan ranking and unranking functions -page.

Notes

  1. D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search (CAGES), CRC Press (1999), Chapter 2, "Generating Elementary Combinatorial Objects" pp. 31--32
  2. L. Moura, Generating Elementary Combinatorial Objects, p. 4

Authorship

The first version of this page was written by Antti Karttunen Aug 8-9, 2012.

Cite this page as

A. Karttunen et al., <a href="http://oeis.org/wiki/Ranking_and_unranking_functions">Ranking_and_unranking_functions</a>, OEIS Wiki.