Computer Science – Computational Complexity
Scientific paper
2006-01-15
published in Discrete Math.and Applications, v.10, n2, 1998
Computer Science
Computational Complexity
Scientific paper
The problem of ranking can be described as follows. We have a set of combinatorial objects $S$, such as, say, the k-subsets of n things, and we can imagine that they have been arranged in some list, say lexicographically, and we want to have a fast method for obtaining the rank of a given object in the list. This problem is widely known in Combinatorial Analysis, Computer Science and Information Theory. Ranking is closely connected with the hashing problem, especially with perfect hashing and with generating of random combinatorial objects. In Information Theory the ranking problem is closely connected with so-called enumerative encoding, which may be described as follows: there is a set of words $S$ and an enumerative code has to one-to-one encode every $s \in S$ by a binary word $code(s)$. The length of the $code(s)$ must be the same for all $s \in S$. Clearly, $|code (s)|\geq \log |S|$. (Here and below $\log x=\log_{2}x)$.) The suggested method allows the exponential growth of the speed of encoding and decoding for all combinatorial problems of enumeration which are considered, including the enumeration of permutations, compositions and others.
No associations
LandOfFree
Fast Enumeration of Combinatorial Objects does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast Enumeration of Combinatorial Objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Enumeration of Combinatorial Objects will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-221657