Cheap and Secure Web Hosting Provider : See Now

[Answers] Splitting permutations into transpositions

, , No Comments
Problem Detail: 

Suppose we are given an array $\texttt{a[]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a[]}$.

Otherwise we interpret $\texttt{a[]}$ as a permutation $\pi:\{0,\ldots, \texttt{max(a[])}\} \to \{0,\ldots, \texttt{max(a[])}\}$ sending $\texttt{i}$ to $\texttt{a[i]}$ for $\texttt{i} \in \{0,\ldots,n-1\}$, and $\pi(k) = k$ for $k\geq \texttt{length(a[])}$.

What could be an algorithm to write $\pi$ as represented by $\texttt{a[]}$ as a sequence of transpositions, and what is the complexity?

Asked By : Dominic van der Zypen

Answered By : Yuval Filmus

One way to do it consists of two steps:

  1. Find the cycle representation of the input.

  2. Convert the cycle representation into a product of transpositions.

The first step is very similar to DFS. The second step is an exercise in permutation group theory.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40667

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback