3
$\begingroup$

I have the following problem:

Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists of all permutations of $x$. We call this set the type class of $x$.

My question:

How to compute the position of $x$ in the lexicographical ordering of $S$?

I found the paper "Enumerative source coding" written by Thomas M. Cover, where this position function $i_{S}$ is shown for binary alphabets (in the following the alphabet is $\{0,1\}$):

$i_S(x_1x_2\cdots x_n)=\sum\limits_{k=1}^{n}x_k\cdot$ $n-k\choose n(w,k)$

with $\;\;n(w,k)=w-\sum\limits_{j=1}^{k-1}x_j\;\;\;$

and $\;\;w$ is the number of occurrences of $1$ in $x\;\;$ ($w=\sum\limits_{k=1}^{n}x_k$).

Unfortunately, i do not know how to extend this formula to alphabets of size $M$. Any help?

$\endgroup$
3
$\begingroup$

This is yet another example of enumerative encoding. Suppose that $x$ has $\alpha_i$ symbols of type $i$. The size of $S$ is then the multinomial coefficient $\binom{n}{\alpha_1,\ldots,\alpha_M}$. Pascal's identity reads $$ \binom{n}{\alpha_1,\ldots,\alpha_M} = \sum_{i\colon \alpha_i \neq 0} \binom{n-1}{\alpha_1,\ldots,\alpha_i-1,\ldots,\alpha_M}. $$ In the lexicographic ordering of $S$, the strings starting with $1$ (if any) constitute the first $\binom{n-1}{\alpha_1-1,\ldots,\alpha_M}$ positions, the strings starting with $2$ (if any) constitute the following $\binom{n-1}{\alpha_1,\alpha_2-1,\ldots,\alpha_M}$ positions, and so on. So $x_1$ already gives you an interval of length $\binom{n-1}{\alpha_1,\ldots,\alpha_{x_1}-1,\ldots,\alpha_m}$ to which $x$ belongs in the lexicographical ordering of $S$. To find its location within the interval, recurse: examine $x_2$, then $x_3$, and so on.

Here is the resulting algorithm, returning a $0$-based position:

  1. Set $P \gets 0$.
  2. For $i=1,\ldots,n$:
    1. Set $P \gets P + \sum_{j < x_i, \alpha_j \neq 0} \binom{n-i}{\alpha_1,\ldots,\alpha_j-1,\ldots,\alpha_M}$.
    2. Set $\alpha_{x_i} \gets \alpha_{x_i} - 1$.
  3. Return $P$.
| cite | improve this answer | |
$\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.