3
$\begingroup$

The definition of inversion vector for permutation is very well defined. Each permutation can be mapped to a unique inversion vector. So is there a well defined inversion vector for each multiset permutation, which maintains such one-to-one correspondence? I'm particularly interested in the multiset permutations where the multiplicity of each element is equal.

Question added:

For permutation, an inversion vector corresponds to a factoradic number, i.e., $i_k∈[0,i−1]$. The decimal number converted from the factoradic number could be used for ranking a permutation. Seems the inversion vector of a multiset permutation looses such good properties as the range of $i_k$ no longer only depends on i ? Or is there a numeral system similar to factoradic numeral system which corresponds to the inversion vector of a multiset permutation?

$\endgroup$
  • $\begingroup$ Did you find a way to rank multisets? Could you share an algorithm or the method you used? $\endgroup$ – Anastasios Andronidis Mar 20 '16 at 23:42
3
$\begingroup$

One can define the inversion vector in the same way and the same proof goes through. Given a multiset $M$ and a multipermutation $\pi=\pi_1\cdots \pi_n$, define its inversion vector to be $i(\pi)=(i_1,i_2,\dots,i_n)$, where $$i_k=\left|\lbrace j \text{ such that } j>k \text{ and } \pi_{k}>\pi_j\rbrace\right|.$$ (notice the strict inequalities)

Theorem: Given $i(\pi)$, we can recover $\pi$.

Proof: Suppose we have determined $\pi_1,\pi_2,\dots, \pi_{k-1}$. Let $M'=M/\lbrace \pi_1,\dots, \pi_{k-1}\rbrace$. We know from $i_{k}$ the number of indices $j$ so that $k+1\le j\le n$ and $\pi_j<\pi_{k}$. So $\pi_{k}$ is greater than exactly $i_k$ elements of $M'$, and is therefore uniquely determined.


Notice that if your multiset is $\lbrace 1^{m_1},\dots,r^{m_r}\rbrace$, then any inversion vector still satisfies $i_k\le n-k$. But clearly not all such vectors can be achieved as the inversion vector of a permutation of $M$. Now, if one tries to write a generating function of inversion vectors, i.e. $\sum_{M} x_1^{i_1}\cdots x_n^{i_n}$ then this won't factor into $\prod P_i(x_i)$ for a general multiset. For example, if $M=\lbrace 1,1,2 \rbrace$ the generating function is $1+x_2+x_1x_2$. This implies that there cannot be a "natural" radix representation to encode these inversion vectors.

All in all, Patricia's comment gives a much quicker way to get around this problem. Just pretend your multiset is actually a set, by giving it a natural total order and then write the permutations as permutations in this new set (this is called the standard permutation corresponding to the multiset permutation).

$\endgroup$
  • 1
    $\begingroup$ Continuing what Gjergji wrote, people often use a process called polarization to convert a multiset permutation where $m_i$ is the multiplicity of the letter $i$ for each $i$ to a permutation in $S_{\sum m_i}$ by replacing the $m_1$ copies of 1 by the numbers $1_1,1_2,\dots ,1_{m_1}$ listed in ascending order, then replacing the 2's from left to right by $2_1,2_2,\dots ,2_{m_2}$, etc. Then declare $i_j < k_l$ in your alphabet iff $i<k$ or if $i=k$ and $j<l$ so you really have a permutation of $1,2,\dots ,\sum m_i$. Then the inversion vector for permutations goes through as Gjergji described. $\endgroup$ – Patricia Hersh Aug 1 '12 at 13:02
  • $\begingroup$ For permutation, an inversion vector corresponds to a factoradic number, i.e., $i_k\in [0, i-1]$. The decimal number converted from the factoradic number could be used for ranking a permutation. Seems the inversion vector of a multiset permutation looses such good properties as the range of $i_k$ no longer only depends on $i$ ? Or is there a numeral system similar to factoradic numeral system which corresponds to the inversion vector of a multiset permutation? $\endgroup$ – Kelvin Lee Aug 1 '12 at 15:02
  • $\begingroup$ I think that introducing factorial expansions is just obscuring the simple method with which one recovers a permutation from its inversion vector. It's likely one can cook up something of that sort for multisets, but I don't see any motivation to do so. $\endgroup$ – Gjergji Zaimi Aug 1 '12 at 15:09
  • $\begingroup$ Sorry maybe this is a little bit off-topic question but I couldn't find any answers anywhere :( I need to rank and unrank a multiset. Is there a way of doing that? Is there any algorithm? $\endgroup$ – Anastasios Andronidis Mar 20 '16 at 21:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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