From: Peter Dalgaard <p.dalgaard_at_biostat.ku.dk>

Date: Tue, 15 Apr 2008 20:56:26 +0200

}

}

table(x)

Date: Tue, 15 Apr 2008 20:56:26 +0200

Martin Maechler wrote:

*> Ok,
*

> thanks a lot, everyone!

*>
**> Yes, I should rather have started thinking a bit more myself,
**> before going the easy route to R-help....
**>
**> Anyway, the most obvious algorithm,
**> just putting things into place by swapping elements,
**> and counting how many times you have to swap, is easy and
**> quite efficient.
**>
**> I'll post R code later, being busy for the next few hours.
**> Martin
**>
**>
*

It is also quite easy to generate the cycles explicitly by a marking
algorithm:

p <- sample(1:100)

x <- integer(100)

for (i in 1:100) {

z <- which(!x)[1]

if (is.na(z)) break

repeat {

x[z] <- i z <- p[z] if (x[z]) break

}

}

table(x)

(the which(!x)[1] bit could be optimized somewhat if this had been C. Notice that the loop is essentially O(N) because every iteration marks one element of x)

*>
*

>>>>>> "MM" == Martin Maechler <maechler@stat.math.ethz.ch>

*>>>>>> on Tue, 15 Apr 2008 18:13:43 +0200 writes:
**>>>>>>
**>
**> MM> I am looking for an algorithm (written in R (preferably) or C,
**> MM> but even pseudo-code in a text book maybe fine)
**> MM> to determine the sign of a permutation.
**>
**> MM> What is that? Well, a permutation is either even or odd, the
**> MM> sign is +1 or -1, respectively, see, e.g.,
**> MM> http://en.wikipedia.org/wiki/Signature_of_a_permutation
**> MM> 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.
**>
**> MM> but I would not know how to algorithmically
**> MM> "write the permutation as a product of disjoint cycles"
**>
**> MM> If you start looking at R code,
**> MM> let's assume the permutation {\pi(i)}_{i=1..n} is simply given
**> MM> as the (integer) vector (\pi(1), \pi(2), ..., \pi(n))
**> MM> {or equivalently, a random permutation is simply found by 'sample(n)'}
**>
**> MM> Thank you in advance for further pointers,
**> MM> or even working R code.
**>
**> MM> Best regards,
**> MM> Martin Maechler, ETH Zurich
**>
**> MM> ______________________________________________
**> MM> R-help_at_r-project.org mailing list
**> MM> https://stat.ethz.ch/mailman/listinfo/r-help
**> MM> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
**> MM> and provide commented, minimal, self-contained, reproducible code.
**>
**> ______________________________________________
**> R-help_at_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.
**>
*

-- O__ ---- Peter Dalgaard ุster Farimagsgade 5, Entr.B c/ /'_ --- Dept. of Biostatistics PO Box 2099, 1014 Cph. K (*) \(*) -- University of Copenhagen Denmark Ph: (+45) 35327918 ~~~~~~~~~~ - (p.dalgaard_at_biostat.ku.dk) FAX: (+45) 35327907 ______________________________________________ R-help_at_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.Received on Tue 15 Apr 2008 - 19:00:12 GMT

Archive maintained by Robert King, hosted by
the discipline of
statistics at the
University of Newcastle,
Australia.

Archive generated by hypermail 2.2.0, at Wed 16 Apr 2008 - 17:30:28 GMT.

*
Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help.
Please read the posting
guide before posting to the list.
*