2
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Have you seen Signature[]? That's vastly easier than counting swaps. $\endgroup$ – J. M. is away Sep 5 '17 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Sep 5 '17 at 17:01
  • $\begingroup$ @J.M., thank you, I thought there would be a function to do it. $\endgroup$ – KraZug Sep 5 '17 at 17:59
6
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – KraZug Sep 5 '17 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.