3
$\begingroup$

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.

The following lattice has 9 unique max length paths from {} to {1,2,3,4,5}, which can be obtained by a depth first search.

lattice(The graph is directed, with arrows pointing down)

Is it possible to write a function that generates the N'th path without enumerating paths 1..N-1.

see: https://math.stackexchange.com/questions/510911/computing-all-simple-paths-in-a-distributive-lattice-in-parallel for more problem details.

$\endgroup$
2
$\begingroup$

Suppose without loss of generality that there is one source $\emptyset$ and one sink $S$. For each node $v$ in your digraph, you can compute recursively the number $N_v$ of unique maximum length paths from $\emptyset$ to $v$: at $\emptyset$ we have $N_\emptyset = 1$, and at other points, $N_v = \sum_u N_u$, where the sum goes over all immediate predecessors of $u$.

This suggests the following encoding for maximal paths at a node $v$. Suppose the immediate predecessors of $v$ are $u_1,\ldots,u_k$, in some arbitrary but fixed order. We will encode all paths as numbers in the range $[0,N_v)$ ($=\{0,\ldots,N_v-1\}$) in the following way: all paths through $u_1$ will be encoded in $[0,N_{u_1})$, all paths through $u_2$ will be encoded in $[N_{u_1},N_{u_1}+N_{u_2})$, and so on. Inside each interval, we apply the same encoding scheme recursively. By applying this scheme for $v = S$ (the sink), we get an efficient encoding system for all maximal paths.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.