[R] Permutations
Torsten Hothorn
Torsten.Hothorn at rzmail.uni-erlangen.de
Tue Sep 26 15:23:37 CEST 2000
> > 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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
More information about the R-help
mailing list