Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2002
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2002

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

Search the Archive

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/



  • 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