[R] Curiously short cycles in iterated permutations with the same seed

[William Dunlap]

Landau's function gives the maximum cycle length of a permutation.
See.,e.g.,
http://mathworld.wolfram.com/LandausFunction.html.

Bill Dunlap
TIBCO Software
wdunlap tibco.com

On Thu, Dec 7, 2017 at 9:34 PM, Eric Berger <ericjberger at gmail.com> wrote:

> 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]]
>
> ______________________________________________
> 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]]