Re: random derangement
- To: mathgroup at smc.vnet.net
- Subject: [mg37425] Re: [mg37416] random derangement
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Mon, 28 Oct 2002 03:40:45 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
On Sun, 27 Oct 2002, DIAMOND Mark R. wrote:
> This is not quite aposite to either NG, but there appear to be none better
> ... My apologies.
>
> I am searching for an algorithm for producing a random derangement of, for
> instance, the integers 1 to approx 10000.
>
> I thought Skiena's site might have such an algorithm, but I could not locate
> one. ... Producing all derangements and choosing one at random is marginally
> beyond the capacity of my machine :-)
>
> Cheers,
>
>
> Mark R. Diamond
You could just repeatedly call RandomPermutation until you get a
derangement.
Needs["DiscreteMath`Combinatorica`"];
RandomDerangement[n_] := Module[{p = {1}}, While[ !DerangementQ[p],
p = RandomPermutation[n]]; p]
The expected number of calls to RandomPermutation is approximately E.
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/