patternModerate
Minimum number of swaps in sorting sequence
Viewed 0 times
sortingnumberminimumsequenceswaps
Problem
Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array?
I've been struggling with this problem for a few months now. I know that the elements are distinct, the answer is the number of cycles in the permutation obtained after normalizing the values and that if the swaps are adjacent bubble sort obtains the optimum number of swaps, but nothing about this one. This question asks the same, but the answers only consider distinct elements.
My approach to the problem is graph theoretical, considering a graph with a node for each element value, drawing an oriented edge from $a$ to $b$ whenever a value $a$ lies at a position where $b$ should lie in the sorted array ($a \neq b$, so no loops), the answer being the maximal (partition with most equivalence classes) partition of the edges into simple cycles (a generalization of the solution for arrays with distinct elements).
Does this problem have a known name? Any references? Any polynomial solution or complexity class ownership (P, NP, graph isomorphism equivalence etc)?
I've been struggling with this problem for a few months now. I know that the elements are distinct, the answer is the number of cycles in the permutation obtained after normalizing the values and that if the swaps are adjacent bubble sort obtains the optimum number of swaps, but nothing about this one. This question asks the same, but the answers only consider distinct elements.
My approach to the problem is graph theoretical, considering a graph with a node for each element value, drawing an oriented edge from $a$ to $b$ whenever a value $a$ lies at a position where $b$ should lie in the sorted array ($a \neq b$, so no loops), the answer being the maximal (partition with most equivalence classes) partition of the edges into simple cycles (a generalization of the solution for arrays with distinct elements).
Does this problem have a known name? Any references? Any polynomial solution or complexity class ownership (P, NP, graph isomorphism equivalence etc)?
Solution
This problem is known as "sorting strings by interchanges". Amir et al [1] proved that the problem is NP-complete and admits a 1.5-approximation. They also obtain other results for transforming two strings into one another (which is not equivalent to the sorting problem) and using several other cost functions for each transformation.
[1]: Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat:
On the Cost of Interchange Rearrangement in Strings. SIAM J. Comput. 39(4): 1444-1461 (2009) -- https://epubs.siam.org/doi/10.1137/080712969
[1]: Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat:
On the Cost of Interchange Rearrangement in Strings. SIAM J. Comput. 39(4): 1444-1461 (2009) -- https://epubs.siam.org/doi/10.1137/080712969
Context
StackExchange Computer Science Q#119293, answer score: 10
Revisions (0)
No revisions yet.