Swaps to Sort an Array 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] =&gt; [(1,4),(2,3)]
[1,3,2,3] =&gt; [(2,3)]
[1,2,1,3,2,3] =&gt; [(2,3),(4,5)]
[1,2,3,4] =&gt; []
[4,2,5,1,3,3] =&gt; [(2,6),(1,5),(1,4),(2,3)]
J, 126 bytes

[:&gt;[:{:"1@}./:~(({.@I.@:~:&gt;@{.)({:@](|.@:{`[`]}~;])[,[:(0{*/,&amp;I.{.)(&lt;0{i.@$)*"1{"0 1=|.@])(,:&gt;@{.))^:(-.@-:&gt;@{.)^:a:;&amp;(0 2$'')


Try it online!

Here is the same code in a more procedural form, if you're looking for an explanation of algorithm.

f=. 3 :0
sorting=.y NB. copy of input we'll mutate
sorted=./:~y
swaps=.0 2$''
for_j. i.#y do.
  correct=.j{sorted
  cur=.j{sorting
  if. cur = correct do.
    continue.
  end.
  NB. correctly fill the current idx j
  valid_idxs=.(j&lt;i.#sorting)
  good_j=. valid_idxs * correct = sorting 
  NB. will any of these be the correct desitnation for the current elm?
  good_dest=. valid_idxs * cur = sorted
  both=.good_j * good_dest
  use=.(1 e.both) { good_j ,: both
  swap_with=. {.I.use
  swaps=.swaps,(j, swap_with)
  sorting=.(sorting {~ swap_with, j) (j, swap_with)} sorting
end.
swaps
)


Try it online!



original answer, doesn't work for repeats

J, 18 bytes

[:;(2]\])&amp;.&gt;@C.@/:


Try it online!

NOTE: Thanks to Neil for pointing out this currently fails on the test case 4 5 2 1 3 3.


/: Grade up, ie, return the permutation that puts the list into order
C.@ Convert that to cyclic permutation form, which uses boxes 
&amp;.&gt; For each of those boxed lists, ie, permutation cycles...
(2]\]) Return all consecutive pairs of two elements.  This gives us the swaps, and it works because J gives the cycle list in descending order.
[:; raze the list of boxes.  This gives us all the swap pairs as a single list of pairs, ie, an N x 2 matrix.