[R] Curiously short cycles in iterated permutations with the same seed
Eric Berger
ericjberger at gmail.com
Fri Dec 8 06:34:48 CET 2017
Hi Boris,
Do a search on "the order of elements of the symmetric group". (This search
will also turn up homework questions and solutions.) You will understand
why you are seeing this once you understand how a permutation is decomposed
into cycles and how the order relates to a partition of n (n=10 in your
case).
Enjoy!
Eric
On Fri, Dec 8, 2017 at 6:39 AM, Boris Steipe <boris.steipe at utoronto.ca>
wrote:
> I have noticed that when I iterate permutations of short vectors with the
> same seed, the cycle lengths are much shorter than I would expect by
> chance. For example:
>
> X <- 1:10
> Xorig <- X
> start <- 112358
> N <- 10
>
> for (i in 1:N) {
> seed <- start + i
> for (j in 1:1000) { # Maximum cycle length to consider
> set.seed(seed) # Re-seed RNG to same initial state
> X <- sample(X) # Permute X and iterate
> if (all(X == Xorig)) {
> cat(sprintf("Seed:\t%d\tCycle: %d\n", seed, j))
> break()
> }
> }
> }
>
> Seed: 112359 Cycle: 14
> Seed: 112360 Cycle: 14
> Seed: 112361 Cycle: 8
> Seed: 112362 Cycle: 14
> Seed: 112363 Cycle: 8
> Seed: 112364 Cycle: 10
> Seed: 112365 Cycle: 10
> Seed: 112366 Cycle: 10
> Seed: 112367 Cycle: 9
> Seed: 112368 Cycle: 12
>
> I understand that I am performing the same permutation operation over and
> over again - but I don't see why that would lead to such a short cycle (in
> fact the cycle for the first 100,000 seeds is never longer than 30). Does
> this have a straightforward explanation?
>
>
> Thanks!
> Boris
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> 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.
>
[[alternative HTML version deleted]]
More information about the R-help
mailing list