MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: random derangement

  • To: mathgroup at
  • Subject: [mg37425] Re: [mg37416] random derangement
  • From: Rob Pratt <rpratt at>
  • Date: Mon, 28 Oct 2002 03:40:45 -0500 (EST)
  • Sender: owner-wri-mathgroup at

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


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

  • Prev by Date: Not quite a Swell FLOOP?
  • Next by Date: Re: Direct tensor algebra
  • Previous by thread: Re: Re: random derangement
  • Next by thread: RE: random derangement