Permutation

Author

Eric W. Weisstein
April 14, 2004

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

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

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

Permutations

?Permutation*

Permutations[Range[2]]

Permutations[Range[3]]

permutations[n_,k_]:=Sort[Flatten[Permutations/@KSubsets[Range[n],k],1]]

4!/2!

permutations[4,2]

Counts

Table[n!,{n,7}]

Length/@Permutations/@Range[7]

Permutations without Rising or Falling

Length/@Table[Select[Permutations[Range[n]],Min[Abs[Subtract@@@Partition[#,2,1]]]>1&],{n,9}]//Timing

Length/@Table[Select[Permutations[Range[n]],Min[Abs[Subtract@@@Partition[#,2,1]]]>1&],{n,8}]//Timing

Combinations

KSubsets[Range[4],2]

Longest Increasing Scattered Subsequence

p=RandomPermutation[10]

LongestIncreasingSubsequence[p]

?Runs

Context[Runs]

Runs[p]

Increasing Runs

p=RandomPermutation[10]

Mean[Table[Take[Length/@Split[RandomPermutation[1000],Less],3],{1000}]]//N

Mean[Table[Take[Length/@Split[RandomPermutation[1000],Less],3],{1000}]]//N

Mean[Table[Take[Length/@Split[RandomPermutation[1000],Less],3],{10000}]]//N//Timing

Mean[Table[Take[Length/@Split[RandomPermutation[1000],Less],3],{10000}]]//N//Timing

Mean[Table[Take[Length/@Split[RandomPermutation[1000],Less],3],{10^5}]]//N//Timing

Differences

<<DiscreteMath`Combinatorica`

Permutations[Range[3]]

Mod[Subtract@@(FromDigits[#,5]&/@{{3,2,1,4},{1,2,3,4}}),4]

KSubsets[Permutations[{1,2,3}],2]

DifferenceDivisible[b_,l_]:=Mod[Subtract@@@Map[FromDigits[#,b]&,KSubsets[Permutations[l],2],
{2}],b-1]

DifferenceDivisible[3,{0,1,1}]

DifferenceDivisible[3,{0,1,2}]

DifferenceDivisible[3,{2,1,2}]

DifferenceDivisible[4,{0,1,1,2}]

DifferenceDivisible[4,{0,1,3,0}]