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?
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.
The array \$A\$, in any necessary form.
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.
[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)]