Since the sort function is not implemented as successive inversions, the parity of the sort operation is not readily available.

Maybe you can determine it somehow by the frequency with which the comparison block is called, but I guess that's not very reliable.

Your best chances is probably to determine the parity youself.

If by "parity of the permutation" you mean the number of elements out of place (or whether that number is even or odd, or the sum of the counts of elements that are on the wrong side of an element over all elements), then I think it's not possible. As Perl uses quicksort as its sorting algorithm, and that sorting algorithm swaps elements across large distances, you can't keep track of the parity in its callback.

You can maybe look at the implementation and infer that Perl will always call the sort block with $a being the left element and $b being the right element in the sequence. But then determining a parity from the number of calls your callback receives and the elements that get compared still strikes me as fragile if even possible at all.

As Perl uses quicksort as its sorting algorithm, and that sorting algorithm swaps elements across large distances,

Oh, please, ditch your 5.6, and enter the 21st century. ;-).

As of 5.8, Perl uses an implementation of mergesort as its default sorting algorithm.

sort

use sort 'stable';          # guarantee stability
use sort '_quicksort';      # use a quicksort algorithm
use sort '_mergesort';      # use a mergesort algorithm
use sort 'defaults';        # revert to default behavior
no  sort 'stable';          # stability not important

use sort '_qsort';          # alias for quicksort
[download]

I think it's about the sign function sgn(σ) of permutations, which tells the parity of necessary transpositions (swapping just two elements)

IMHO it should be simple to reproduce and count these transpositions by comparing input and output of the sorting so it's O(n).

Faint memories tell me that counting the numbers of elements which need to be "pushed forward" is already enough.¹

Cheers Rolf

¹) Never mind, this was wrong! For {4,3,2,1} it's even and for {4,3,1,2} it's odd.

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]

If you managed to obtain this information, what would you do with it?

That is, do you want it for its own sake, or is there some practical use for it that might be satisfied in some alternate way?

BrowserUk:

Are you sure that this is a useful question? It may be unexpectedly offensive to the OP and cause somewhat of a ruckus.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

I don't think this is offensive. It's basically asking if this is an XY Problem, which is often a good question.

Perl 6 - second systems done right

Are you sure that this is a useful question?

I don't know. That's up to the OP to determine.

Since the information he has asked for isn't practically available, it makes sense to consider the possibility of alternate ways of achieving his final goal.

Of course, if what he has asked for is his final goal, then no alternative will do.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

“Let’s not go there, shall we?”   BrowserUK’s point is, or could be, a valid one.   And so, I will always assume only the best of intentions from anyone and everyone who meditates in this castle:   “It is valid, and honorably bespoke.”

You might not be able to obtain the “parity” of a sort algorithm in the traditional sense ... and, like BrowserUK, I rather wonder for what purpose you actually need it.   Perhaps some kind of record-by-record comparison of the original vs. the sorted streams might produce a useful alternative metric.

Is the purpose of the OP’s question to ascertain some useful characteristic of the data, or of a particular algorithm?   If Perl no longer uses that algorithm (which is undoubtedly the case), does this invalidate the question as-asked?   (If it does, then we need to find an alternate question to ask, such that the answer, although a different answer, serves the same useful purpose.)

Thank you for this question.

I want to do computations in anticommutative algebras (ab=-ba). This anticommutativity guarantees that all elements are nilpotent (a^2=0). In order to know if two elements are the same, I wanted to order them, keeping track of permutations, the compare them stringwise (abc=cab). My main problem was to compute products (i.e string concatenations) then sorting them and multipliying by the parity for the sort permutation.

Thanks to your question, i realized that i was doing too much. If I have two ordered monomials 'abde' and 'chk', i can count for each letter of the first, how many leters for the second are smaller than it. That way i can easily keep track for parity.

But then I realized something cooler. If my algebra has N (ordered) generators (a1,..,an), i can represent each monomial(basis) with a number between 0 and 2^(n+1)-1 by taking its binary representation.

Thanks for all the help guys.

Skipping over all the bits of that I didn't understand...

YW :)

#!/usr/bin/perl

use strict;
use warnings;
use Algorithm::FastPermute qw(permute);

my(@array) = (1, 2, 3,4);

my $i = 0;
permute { while (++$i){return} } @array ;
foreach my $number(@array) {
    if (($number % 2) == 0) {
        print "even\n";
    }
    else {
        print "odd\n";
    }
}
[download]

returns:
odd
even
odd
even
[download]

Is that the same as the sign of the permutation (SignPerm ... Hm, yep, I guess so)? You may want to check out GAP (or sage which includes GAP). Perl is great, but sometimes it is helpful to have a system where a permutation is a native object. :)