Swaps to Sort an Array
J, 126 bytes
[:>[:{:"1@}./:~(({.@I.@:~:>@{.)({:@](|.@:{`[`]}~;])[,[:(0{*/,&I.{.)(<0{i.@$)*"1{"0 1=|.@])(,:>@{.))^:(-.@-:>@{.)^:a:;&(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<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]\])&.>@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 orderC.@Convert that to cyclic permutation form, which uses boxes&.>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.
Jelly, 51 43 bytes
ṪµṢ,$Ḣ©€E¬a="ʋṚƊ×\ẸÞṪTḢ,®ṛ¦Ẹ}¡@¥
WÇẸпFĖẠƇÄ
Try it online!
A pair of links which when called as a monad returns a list of pairs of 1-indexed indices to swap. Based on the clever J algorithm developed by @Jonah, so be sure to upvote that one too!
Explanation
Helper link
Takes a list containing a list of the remaining items to be sorted, optionally preceded by the most recent swap. Takes full advantage of the way that Ḣ (Head) and Ṫ (tail) pop items from a list, which for someone from an R background was something I found took some getting used to when I started using Jelly!
Ṫ | Tail (yields the list of remaining items, and also removes this from the list that п is collecting up)
µ | Start a new monadic chain
Ṣ,$ | Pair the sorted list with the unsorted remaining items
Ḣ©€ | Take the head of each, removing from the list and storing each in turn in the register (so the register is left holding the head of the unsorted list)
Ɗ | Following as a monad
ʋṚ | - Following as a dyad, using a list of the remaining sorted and unsorted lists (in that order) as right argument
E | - Equal (i.e. the head of the unsorted and sorted lists matches)
¬ | - Not
a | - And:
=" | - Equal to zipped right argument (effectively a logical list indicating which of the remainder of the sorted list matched the head of the unsorted and vice-versa)
×\ | Cumulative product
ẸÞ | Sort by whether any true
Ṫ | Tail
T | Convert to list of truthy indices
Ḣ | Head (will be 0 if the head of the unsorted and sorted lists matches)
¥ | Following as a dyad, using the remaining unsorted list as right argument
, | Pair the index to swap with:
@ | - Following with arguments reversed:
Ẹ}¡ | - Run following once if index to swap is nonzero:
®ṛ¦ | - Replace item at index to swap with the original head of the unsorted list that was stored in the register
Main link, takes a list to be sorted
W | Wrap in a further list
Ẹп | While any non-zero, do the following collecting up intermediate results
Ç | - Call helper link
F | Flatten (will remove the now empty initial list)
Ė | Enumerate (pair the index of each with the item)
ẠƇ | Keep only those without zeros
Ä | Cumulative sum of each pair
Original algorithm that fails with repeated values, 16 bytes
ỤịƬ€`Ṣ€ŒQTịƲṡ€2Ẏ
Try it online!
A monadic link taking a list of integers and returning a list of lists of integers representing the 1-indexed swaps.
Explanation
Ụ | Grade the list z up, i.e., sort its indices by their corresponding values.
Ƭ€` | For each member of the resulting list, do the following until no new values, using the list of indices itself as the right argument. Keep all intermediate values.
ị | - Index into list
Ʋ | Following as a monad:
Ṣ€ | - Sort each list
ŒQ | - Logical list, true for original copy of each unique value
T | - Indices of truthy values
ị | - Index into list
ṡ€2 | Split each into overlapping sets of 2
Ẏ | Join outer together
Inefficient algorithm that is too slow for long lists with lots of repeats, 27 bytes
ĠŒ!€ŒpµFịƬ€`Ṣ€ŒQTịƲṡ€2Ẏ)LÞḢ
Try it online!
Wolfram Language (Mathematica), 219 188 184 bytes
F@A_:=MinimalBy[##&@@@f/@#[[1]]&@*(FindPermutation@A~PermutationProduct~#&)/@GroupElements@PermutationGroup[Cycles@*List/@Join@@((f=Partition[#,2,1]&)/@Values@PositionIndex@A)],Length]
Try it online!
-31 bytes thanks to @Chris
-4 bytes by making the code much faster (no more GroupSetwiseStabilizer slowness)
Thanks to @NickKennedy for pointing out that the first version failed on non-unique list entries. The present version is a tour-de-force that calculates the permutation group that leaves the list unchanged, then tries each element of this group to see if it can be used to shorten the result.
This code still goes very slowly on massively duplicated lists.
Explicit code:
A = {4,5,2,1,3,3,10,9,7,6,8,8}
(* compute the indices of equal elements *)
Q = Values[PositionIndex[A]]
(* compute the permutation group that leaves A invariant *)
G = PermutationGroup[Cycles@*List /@ Join @@ (Partition[#, 2, 1] & /@ Q)]
(* find the permutation that sorts A and combine it with every element of G *)
F = PermutationProduct[FindPermutation[A], #] & /@ GroupElements[G]
(* convert every resulting permutation to the desired form *)
J = Join @@ (Partition[#, 2, 1] & /@ #[[1]]) & /@ F
(* pick the shortest solutions *)
MinimalBy[J, Length]