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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Did you find a way to rank multisets? Could you share an algorithm or the method you used? $\endgroup$
    – Anastasios Andronidis
    Commented Mar 20, 2016 at 23:42

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
4
  • 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
    Commented Aug 1, 2012 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
    Commented Aug 1, 2012 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
    Commented Aug 1, 2012 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
    Commented Mar 20, 2016 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .