c++ - Number of swaps in a permutation -

this question has answer here:

• counting adjacent swaps required convert 1 permutation another 6 answers

is there efficient algorithm (efficient in terms of big o notation) find number of swaps convert permutation p identity permutation i? swaps not need on adjacent elements, on elements.

so example:

i = {0, 1, 2, 3, 4, 5}, number of swaps 0 p = {0, 1, 5, 3, 4, 2}, number of swaps 1 (2 , 5) p = {4, 1, 3, 5, 0, 2}, number of swaps 3 (2 5, 3 5, 4 0) 

one idea write algorithm this:

int count = 0; for(int = 0; < n; ++ i) {     for(; p[i] != i; ++ count) { // permuted multiple times         std::swap(p[p[i]], p[i]);         // number @ hand should     } } 

but not clear me whether guaranteed terminate or whether finds correct number of swaps. works on examples above. tried generating permutation on 5 , on 12 numbers , terminates on those.

this problem arises in numerical linear algebra. matrix decompositions use pivoting, swaps row greatest value next row manipulated, in order avoid division small numbers , improve numerical stability. decompositions, such lu decomposition can later used calculate matrix determinant, sign of determinant of decomposition opposite of original matrix, if number of permutations odd.

edit: agree question similar counting adjacent swaps required convert 1 permutation another. argue question more fundamental. converting permutation 1 can converted problem inverting target permutation in o(n), composing permutations in o(n) , finding number of swaps there identity. solving question explicitly representing identity permutation seems suboptimal. also, other question had, until yesterday, 4 answers single 1 (by |\/|ad) seemingly useful, description of method seemed vague. user lizusek provided answer question there. don't agree closing question duplicate.

edit2: proposed algorithm seems rather optimal, pointed out in comment user rcgldr, see answer counting adjacent swaps required convert 1 permutation another.

i believe key think of permutation in terms of cycle decomposition.

this expresses permutation product of disjoint cycles.

key facts are:

1. swapping elements in 2 disjoint cycles produces 1 longer cycle
2. swapping elements in same cycle produces 1 fewer cycle
3. the number of permutations needed n-c c number of cycles in decomposition

your algorithm swaps elements in same cycle correctly count number of swaps needed.

if desired, can in o(n) computing cycle decomposition , returning n minus number of cycles found.

computing cycle decomposition can done in o(n) starting @ first node , following permutation until reach start again. mark visited nodes, start again @ next unvisited node.