Assume this input. 

my @x = qw"q s t l y a p c f v i r d w k o j b";

[download]

First, sort in such a way that you get the permutation too, not only the sorted array. We'll use perl's builtin sort for this, though there are certainly other ways. 

my @p = sort { $x[$a] cmp $x[$b] } 0 .. @x-1;

[download]

Now @p contains the permutation, eg. it contains (5, 17, 7, ...) because the first element of the sorted array would be $x[5] (that is, "a"), the second would be $x[17] etc. If you need it, @x[@p] gives the sorted list.

Now you just have to determine the parity of this permutation. As hinted in Knuth exercises 5.2.2/2 and 5.3.1/29, a way to do this is to determine the number of cycles in the permutation (by traversing them), and then subtracting this number from the number of elements. The following may or may not work, be sure to verify it's correct before using it. 

my $d = 0; my @s; 
for my $s (0 .. @p - 1) { 
    if ($s[$s]) { $d++; } 
    for (my $t = $s; !$s[$t]++; $t = $p[$t]) {} 
} 
if (0 != $d%2) 
    { say "odd" } else { say "even" }

[download]

Alternately, you could try to use some module, such as Math::GSL, but it doesn't seem like it gets much easier that way.

Update: or you could interface some external computer algebra software that has a library function for this. Here's a hilariously bad example. 

use File::Temp "tempfile"; 
my($T, $N) = tempfile("perm-XXXXXXXX", UNLINK => 1); 
say $T "SignPerm(PermList(1+[", join(",", @p), "]));\n"; 
close $T or die; 
my $s = qx"gap -q <$N"; 
if (1 == $s) { say "even" } elsif (-1 == $s) { say "odd" } else { die 
+}

[download]

In reply to Re: sort function and parity of the permutation. by ambrus
in thread sort function and parity of the permutation. by latejita

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.