5
You are given an array \$A\$, which may contain duplicate elements. In each swap, you may swap the value of any two indices \$i, j\$ (i.e. switch the values of \$A_i\$ and \$A_j\$). What is the least amount of swaps needed to sort the array, and what are the corresponding swapped indices?
Scoring
This is code-golf, so shortest code wins. However, your program must terminate in reasonable time (less than 10 seconds) for any array \$A\$ with less than 1000 elements.
Input
The array \$A\$, in any necessary form.
Output
A list of swaps, with each swap being a pair of numbers, in sequential order - first pair in list is swapped first, in any necessary form.
In the output, the numbers should all represent indices. You may output the answer either one-indexed or zero-indexed, but my samples will use one-indexing.
The answer might not be unique. However, your answer should still have the same length as the optimal sequence of swaps.
Test cases
[4,3,2,1] => [(1,4),(2,3)]
[1,3,2,3] => [(2,3)]
[1,2,1,3,2,3] => [(2,3),(4,5)]
[1,2,3,4] => []
[4,2,5,1,3,3] => [(2,6),(1,5),(1,4),(2,3)]
Yes, yes, and yes (although there may be more than one optimal sequence, yours should still have the same length as the optimal sequence) – Baaing Cow – 2019-12-28T03:23:27.943
1Can you please add more and longer test cases? – Jonah – 2019-12-28T08:07:59.450
1@Jonah Done. Although the samples may be quite a bit suggestive... – Baaing Cow – 2019-12-28T08:37:52.670
1Per @Neil's comment on my answer, can you please add the test case
4,5,2,1,3,3
with expected length 4.(1 5) (0 4) (0 3) (1 2)
is one possible (0-indexed) solution. This test case ensures that you can't just use the same algorithm that works for the "no repeats" case. – Jonah – 2019-12-28T18:48:00.0031@BaaingCow are you sure this is possible within 10 seconds when there are multiple identical numbers, as per comments below the J and Jelly answers? – Nick Kennedy – 2019-12-28T18:48:11.457
On second thought, it seems that my reference solution is wrong - whoops :| My code also returns an swap sequence of length 5 for
4,5,2,1,3,3
. Are challenges with no reference solution allowed? – Baaing Cow – 2019-12-29T03:52:51.823An more readable algorithm is available at https://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence/15152602#15152602 However, it doesn't handle arrays with duplicates well. So it could perhaps be tweaked to do that. Or another approach is necessary.
– Kjetil S. – 2019-12-29T06:48:51.077@BaaingCow You don't need a reference solution, but you do need correct test cases. I believe my edited answer is now correct, and I included a reference version of the algorithm. It found shorter solutions for both of the longer test cases you had previously posted. – Jonah – 2019-12-30T08:57:50.220