# Sort list but keeping the number of swaps required

I have a set of lists that I want to put into ordered form, but I need to know how many swaps are required to put them into order - these are indexes for minors of a determinant, so each swap gives a factor of (-1).

For instance, if I have $\phi(\{5,3,2,1,4\})$, I need to return $-\phi(\{1,2,3,5,4\})$. I've written the following, which does what I need but really inelegantly:

reprules = {ϕ[{a_, b_, c_, d_, e_}] /; e < d -> (-1) ϕ[{a, b, c, e, d}],
ϕ[{a_, b_, c_, d_, e_}] /; d < c -> (-1) ϕ[{a, b, d, c, e}],
ϕ[{a_, b_, c_, d_, e_}] /; c < b -> (-1) ϕ[{a, c, b, d, e}],
ϕ[{a_, b_, c_, d_, e_}] /; b < a -> (-1) ϕ[{b, a, c, d, e}]};

ϕ[{5, 3, 2, 1, 4}] //. reprules

(* -ϕ[{1, 2, 3, 4, 5}] *)

ϕ[{5, 3, 2, 1, 8}] //. reprules

(* ϕ[{1, 2, 3, 5, 8}] *)


As usual, I find myself sure there will be a way to do this neatly but can't figure it out. A solution should work without knowledge of the number of arguments. I could hack something out of FindPermutation by the looks of it, but it won't be pretty either.

• Have you seen Signature[]? That's vastly easier than counting swaps. – J. M. is away Sep 5 '17 at 16:00
• Also, much easier to compute than the minimal number of swaps required. Sorting can be done with more or fewer swaps, but odd/even nature of the number is invariant. – Szabolcs Sep 5 '17 at 17:01
• @J.M., thank you, I thought there would be a function to do it. – KraZug Sep 5 '17 at 17:59

As J. M. implied you can use Signature:

The signature of the permutation is $(-1)^n$, where $n$ is the number of transpositions of pairs of elements that must be composed to build up the permutation.

rep = ϕ[a_List] :> Signature[a] ϕ[Sort[a]];

ϕ[{5, 3, 2, 1, 4}] /. rep
ϕ[{5, 3, 2, 1, 8}] /. rep

-ϕ[{1, 2, 3, 4, 5}]

ϕ[{1, 2, 3, 5, 8}]


By the way your original rule set could be condensed to a single rule like this, with the advantage of working with an arbitrary number of arguments as well:

rep2 = ϕ[{x___, a_, b_, y___}] /; b < a :> (-1) ϕ[{x, b, a, y}];

ϕ[{5, 3, 2, 1, 4}] //. rep2

ϕ[{5, 3, 2, 1, 8}] //. rep2

• Thank you, that is exactly the function that I needed. And yes, I hadn't thought about the bad implementation of bubble sort particularly, it did what I needed to continue in the few hours before someone told me what the right function was. – KraZug Sep 5 '17 at 18:01