[R] Permutations

[Torsten Hothorn]

> > Consider the set of all permutations of 1:N (=: S, say) and a fixed
> > element a from S. I now need to compute the number of permutations s from
> > S which are elementwise less or equal to a: | { s \in S | s <= a } |
> > 
> > Of cource, backtracking using a tree structure is possible. Does anyone
> > know an efficient way?
> 
> Er, "elementwise less than or equal"? Maybe I got off on the wrong
> foot today, but if you mean what I think you mean, I get
> 
> N can only be where it is in  a  or it would replace something smaller
> N-1 could be where it is or where N was, but N mustn't move
> ...
> 
> I.e. I'd get the answer to be 1, namely a itself.


Well, here is (hopefully) the right problem:

consider again the set S of all permutations of 1:N. There is a 1:1
connection between a permutation s from S and the vector of its cumulative
sum: cumsum(s) = (s_1, s_1 + s_2, ..., s_1 +...s_N). Now one has a fixed
permutation a and therefore cumsum(a). The question is: if all permutations
have probability 1/N!, what is P(cumsum(s) <= cumsum(a)), in other words:
how many permutations s in S have cumsum(s) <= cumsum(a), elementwise ?

Example:

N = 3

permutation	cumsum
1 2 3	      1 3 6	*
1 3 2         1 4 6	*
2 1 3         2 3 6	*
2 3 1         2 5 6	*   
3 1 2         3 4 6
3 2 1         3 5 6
 
a := 2 3 1 => cumsum(a) = 2 5 6 and P(cumsum(s) <= cumsum(a)) = 4/6 (those
with * are the good ones)

Thanks for *ANY* hint ;-)

Torsten

 

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._