Let $S_n$ be the set of all permutations of integers from $1$ to $n$. Let $P_1$ and $P_2$ be two partitions defined on $S_n$ as follows.

$P_1$ is the set of all those permutations which have even number of cycles. $P_2$ is the set of all those permutations which have odd number of cycles. The sets $P_1$ and $P_2$ have a lexicographic ordering imposed on them.

Given a permutation $P$

  1. Tell which partition it belongs to
  2. What is the lexicographic rank($1$ based indexing) of this permutation in that partition. If this rank is $K$, you have to specify the number $K$ mod $M$ where $M = 1000000007 (1e9 + 7)$

Here $N$ can be as large as $10^5$

My approach: Calculate the number of cycles in P using a simple DFS technique on my computer and decide which partition it belongs to. For calculating rank I first calculate its rank in the set $S_n$ Let that rank be $K_1$($1$ based indexing) then the actual rank is coming out to be floor($\frac{K_1+1}{2}$). I am having trouble applying modular arithmetic on this expression. Is there any other way to solve this problem?

Note: By "cycle" I mean when the permutation is represented as a graph, the number of components or disjoint forests formed.

  • $\begingroup$ @AndrásSalamon I have corrected the question $\endgroup$ – lassaendie Oct 5 '15 at 11:41

I assume by "even length cycles" and "odd length cycles" you mean the Parity/Sign of a permutation ( https://en.wikipedia.org/wiki/Parity_of_a_permutation ). In this case you might use one of the following methods to compute it: https://mathoverflow.net/questions/72669/finding-the-parity-of-a-permutation-in-little-space


For the other question: Determining the lexicographic ordering of the permutation you could use the Factorial Number system and the Lehmer-Code: https://en.wikipedia.org/wiki/Factorial_number_system#Permutations

See for example : http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html for a Python-Implementation of the Lehmer-Code and related Factorial-Number System.


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.