Number of swaps in a permutation [duplicate]

Question

This question already has answers here:

Counting the adjacent swaps required to convert one permutation into another (6 answers)

Closed 5 years ago.

Is there an efficient algorithm (efficient in terms of big O notation) to find number of swaps to convert a permutation P into identity permutation I? The swaps do not need to be on adjacent elements, but on any elements.

So for example:

I = {0, 1, 2, 3, 4, 5}, number of swaps is 0
P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5)
P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0)

One idea is to write an algorithm like this:

int count = 0;
for(int i = 0; i < n; ++ i) {
    for(; P[i] != i; ++ count) { // could be permuted multiple times
        std::swap(P[P[i]], P[i]);
        // look where the number at hand should be
    }
}

But it is not very clear to me whether that is actually guaranteed to terminate or whether it finds a correct number of swaps. It works on the examples above. I tried generating all permutation on 5 and on 12 numbers and it always terminates on those.

This problem arises in numerical linear algebra. Some matrix decompositions use pivoting, which effectively swaps row with the greatest value for the next row to be manipulated, in order to avoid division by small numbers and improve numerical stability. Some decompositions, such as the LU decomposition can be later used to calculate matrix determinant, but the sign of the determinant of the decomposition is opposite to that of the original matrix, if the number of permutations is odd.

EDIT: I agree that this question is similar to Counting the adjacent swaps required to convert one permutation into another. But I would argue that this question is more fundamental. Converting permutation from one to another can be converted to this problem by inverting the target permutation in O(n), composing the permutations in O(n) and then finding the number of swaps from there to identity. Solving this question by explicitly representing identity as another permutation seems suboptimal. Also, the other question had, until yesterday, four answers where only a single one (by |\/|ad) was seemingly useful, but the description of the method seemed vague. Now user lizusek provided answer to my question there. I don't agree with closing this question as duplicate.

EDIT2: The proposed algorithm actually seems to be rather optimal, as pointed out in a comment by user rcgldr, see my answer to Counting the adjacent swaps required to convert one permutation into another.

Answer 1

I believe the following are true:

If S(x[0], ..., x[n-1]) is the minimum number of swaps needed to convert x to {0, 1, ..., n - 1}, then:

1. If x[n - 1] == n - 1, then S(x) == S(x[0],...,x[n-2]) (ie, cut off the last element)
2. If x[-1] != n - 1, then S(x) == S(x[0], ..., x[n-1], ..., x[i], ... x[n-2]) + 1, where x[i] == n - 1.
3. S({}) = 0.

This suggests a straightforward algorithm for computing S(x) that runs in O(n) time:

int num_swaps(int[] x, int n) {
  if (n == 0) {
    return 0;
  } else if (x[n - 1] == n  - 1) {
    return num_swaps(x, n - 1);
  } else {
    int* i = std::find(x, x + n, n - 1);
    std::swap(*i, x[n - 1])
    return num_swaps(x, n - 1) + 1;
  }
}

Answer 2

I believe the key is to think of the permutation in terms of the cycle decomposition.

This expresses any permutation as a product of disjoint cycles.

Key facts are:

1. Swapping elements in two disjoint cycles produces one longer cycle
2. Swapping elements in the same cycle produces one fewer cycle
3. The number of permutations needed is n-c where c is the number of cycles in the decomposition

Your algorithm always swaps elements in the same cycle so will correctly count the number of swaps needed.

If desired, you can also do this in O(n) by computing the cycle decomposition and returning n minus the number of cycles found.

Computing the cycle decomposition can be done in O(n) by starting at the first node and following the permutation until you reach the start again. Mark all visited nodes, then start again at the next unvisited node.