Worst-case number of transpositions needed to generate a permutation For a permutation on $n$ elements, what is the worst-case minimal number of transpositions that need to be multiplied to give the permutation? The transpositions do not need to be adjacent.
 A: The number is indeed $n- s$, where $s$ is the number of disjoint cycles, or, equivalently: 
$$L(\sigma)=\sum_{c_i} ( l(c_i) -1) $$ if $\sigma= c_1 c_2 \ldots $ is the expression of $\sigma$ as a product of disjoint cycles. 
The decomposition of a permutation into product of disjoint cycles changes by passing from $\sigma$ to $\tau \sigma$, where $\tau$ is a transposition as follows: if the support of $\tau$ is contained in the support of one of the $c$ then $\tau c = c' c''$, where the supports of $c$ is partitioned into the support of $c'$ and $c''$, while if the support of $\tau$ is contained in the union of $c'$, $c''$, then $\tau c' c''= \tau c$. Therefore:
$$L(\tau \sigma) = \begin{cases} L(\sigma) -1 \textrm{ if $\tau$ slices a cycle of $\sigma$ } \\
L(\sigma) + 1 \textrm{ if $\tau$ joins two cycles of $\sigma$}\end{cases} $$
We see now that any permutation can be written as a product of $L(\sigma)$
( and no less) transpositions ( we can decrease the $L$ by multiplying on the left with transpositions, till $L$ gets to $0$, that is, till we get the identity permutation), and moreover, the number of such transpositions is $\equiv L(\sigma) \mod 2$. 
$\bf{Added:}$  How many transpositions has one to multiply a permutation by to obtain the identity permutation? Every time we multiply by a transposition the number of cycles can increase by at most $1$ ( and the number does vary by $1$). To get $n$ cycles from the original one, we need to multiply by $n-s$ transpositions -- properly chosen.
A: Hint:  each transposition can put an element in its place, but the answer is not $n$
