Lexicographical position of a string in its type class
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:


Set $P \gets 0$.
For $i=1,\ldots,n$:

Set $P \gets P + \sum_{j &lt; x_i, \alpha_j \neq 0} \binom{n-i}{\alpha_1,\ldots,\alpha_j-1,\ldots,\alpha_M}$.
Set $\alpha_{x_i} \gets \alpha_{x_i} - 1$.

Return $P$.