I consider even permutations of $n$ numbers. There are $n!/2$ even permutations.
I need to represent these permutations in a computer program as an integer between $0$ and $\frac{n!}{2} - 1$.
A theoretical procedure converting an even permutation into a number could enumerate all preceding permutations and count how many of them are even. But this procedure would be too slow for practical purposes. Is there a faster procedure to encode and decode even permutations (possibly with different encoding) in this range ?
It is not hard to see that the lexicographical order of permutation $a_1,a_2,\dots,a_n$ is $\sum\limits_{i=1}^{n-2} \frac{f_i(n-i)!}{2}$ where $f_i$ is the number of values that are smaller than $a_i$ and to the right of $a_i$.
using this formula we can clearly find the lexicographical order of a permutation in time $\mathcal O( n\log(n))$ .
You can also find the permutation with a certain value in time $\mathcal O(n\log(n))$ by going from left to right and selecting what value to insert ( use a data structure that allows you find the $k$'th smallest unused element). After selecting the first $n-2$ elements just order the final two so that the permutation is even.