Random Permutation

Author

Eric W. Weisstein
February 24, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/RandomPermutation.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RandomPermutation.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<DiscreteMath`Combinatorica`

Code

MyRandomPermutation[n_Integer?Positive] := Ordering[Table[Random[], {n}]]

IncreasingBlocks[l_List]:=Select[Split[Less@@@Partition[l,2,1]],And@@#&]

Average number of length-1 cycles

With[{g=AlternatingGroup[26]},Mean[26-RandomPermutation[g,10^4]/.Cycles[l_]:>Total[Length/@l]]]

With[{g=CyclicGroup[26]},Mean[26-RandomPermutation[g,10^4]/.Cycles[l_]:>Total[Length/@l]]]

With[{n=10},Mean[n-RandomPermutation[n,10^4]/.Cycles[l_]:>Total[Length/@l]]]

With[{n=26},Mean[n-RandomPermutation[n,10^4]/.Cycles[l_]:>Total[Length/@l]]]

With[{g=MathieuGroupM11[]},Mean[GroupOrder[g]-RandomPermutation[g,10^4]/.Cycles[l_]:>Total[Length/@l]]]

Average Number of Inversions

Mean/@Map[Inversions,Table[RandomPermutation[n],{n,6},{10000}],{2}]//N//Timing

Table[n(n-1)/4.,{n,6}]

Number of Increasing Blocks

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[2]]],{100000}]/100000.]

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[5]]],{10000}]/10000.]

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[10]]],{10000}]/10000.]

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[50]]],{10000}]/10000.]

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[100]]],{5000}]/5000.]

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[500]]],{1000}]/1000.]

Timing[Plus@@Table[Length[IncreasingBlocks[RandomPermutation1[1000]]],{1000}]/1000.]

l={{2,0.49734},{5,1.4951},{10,3.159},{50,16.4963},{100,33.179},{500,166.49},{1000,333.186}}

Divide@@@l

ListPlot[l,PlotJoined->True,AxesOrigin->{0,0},PlotRange->All]