1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.