Counting the adjacent swaps required to convert one permutation into another

by

Regarding the minimum number of (not necessarily adjacent) swaps needed to convert a permutation into another, the metric you should use is the Cayley distance which is essentially the size of the permutation – the number of cycles.

Counting the number of cycles in a permutation is a quite trivial issue. A simple example. Suppose permutation 521634.

If you check the first position, you have 5, in the 5th you have 3 and in the 3rd you have 1, closing the first cycle. 2 is in the 2nd position, so it make a cycle itself and 4 and 6 make the last cycle (4 is in the 6th position and 6 in the 4th). If you want to convert this permutation in the identity permutation (with the minimum number of swaps), you need to reorder each cycle independently. The total number of swaps is the length of the permutation (6) minus the number of cycles (3).

Given any two permutations, the distance between them is equivalent to the distance between the composition of the first with the inverse of the second and the identity (computed as explained above). Therefore, the only thing you need to do is composing the first permutation and the inverse of the second and count the number of cycles in the result. All these operations are O(n), so you can get the minimum number of swaps in linear time.

More Related Contents:

  1. Custom Weighted Scale [closed]
  2. How do I search for a number in a 2d array sorted left to right and top to bottom?
  3. Quicksort: Choosing the pivot
  4. Generate an integer that is not among four billion given ones
  5. Breadth First Vs Depth First
  6. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  7. Time complexity of Euclid’s Algorithm
  8. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  9. What is the fastest integer factorization algorithm?
  10. Is there an algorithm for color mixing that works like mixing real colors?
  11. Algorithm to list unique permutations of string with duplicate letters
  12. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  13. Collision detection of huge number of circles
  14. The sieve of Eratosthenes in F#
  15. Fuzzy date algorithm
  16. Most efficient way to calculate Levenshtein distance
  17. Compute rank of a combination?
  18. Efficiently selecting a set of random elements from a linked list
  19. reconstructing a tree from its preorder and postorder lists
  20. Find if a point is inside a convex hull for a set of points without computing the hull itself
  21. Why do we ignore co-efficients in Big O notation?
  22. Myers diff algorithm vs Hunt–McIlroy algorithm
  23. Given Prime Number N, Compute the Next Prime?
  24. Randomly choosing from a list with weighted probabilities
  25. Planar Graph Layouts
  26. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  27. Compute the area of intersection between a circle and a triangle?
  28. Unbiased random number generator using a biased one
  29. Quadratic algorithm for 4-SUM
  30. CUDA stream compaction algorithm

Leave a Comment