Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 RandomDerangement

Source Notebook

Find a random derangement of the numbers 1 through n

Contributed by: Dr. Major Bobby R. Treat (USAF, Ret.)

ResourceFunction["RandomDerangement"][n]

gives a random derangement of the counting numbers 1 through n.

Details and Options

A derangement on the numbers 1,…,n is a permutation p satisfying pi≠i for i=1,…,n.
A derangement is also referred to as a fixed-point-free permutation.

Examples

Basic Examples (2) 

Get a random derangement of 1,…,10:

In[1]:=
der = ResourceFunction["RandomDerangement"][10]
Out[1]=

Confirm that the result is a derangement:

In[2]:=
(der[[#]] != #) & /@ der
Out[2]=

Scope (3) 

RandomDerangement is on average linear-time in the number of elements:

In[3]:=
timings = Table[First[ AbsoluteTiming[ResourceFunction["RandomDerangement"][2^n]]], {n, 15, 25}]
Out[3]=

Check that successive quotients are all approximately two:

In[4]:=
Divide @@@ Reverse /@ Partition[timings, 2, 1]
Out[4]=

Check that the base-2 logarithms of the timings versus n lie on a line of slope 1:

In[5]:=
ListPlot[Transpose[{Range[15, 25], Log[2, timings]}], AspectRatio -> 1]
Out[5]=

Version History

  • 1.0.0 – 22 April 2020

License Information