[R] sign(<permutation>) in R ?

[Peter Dalgaard]

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 at 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