I am looking for an algorithm (written in R (preferably) or C, but even pseudo-code in a text book maybe fine) to determine the sign of a permutation.
What is that? Well, a permutation is either even or odd, the sign is +1 or -1, respectively, see, e.g., http://en.wikipedia.org/wiki/Signature_of_a_permutation which also says >> In practice, in order to determine whether a given permutation >> is even or odd, one writes the permutation as a product of >> disjoint cycles. The permutation is odd if and only if this >> factorization contains an odd number of even-length cycles. but I would not know how to algorithmically "write the permutation as a product of disjoint cycles" If you start looking at R code, let's assume the permutation {\pi(i)}_{i=1..n} is simply given as the (integer) vector (\pi(1), \pi(2), ..., \pi(n)) {or equivalently, a random permutation is simply found by 'sample(n)'} Thank you in advance for further pointers, or even working R code. Best regards, Martin Maechler, ETH Zurich ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.