Costas Array

Author

Eric W. Weisstein
March 21, 2006

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

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

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

Code

DifferenceTable[l_List]:=Module[{n},
Table[Take[l,-n]-Take[l,n],{n,Length[l]-1,1,-1}]
]

CostasQ[l_List]:=If[Length[l]==2,
And@@(SameQ[Union[#],#]&/@Sort/@DifferenceTable[l]) ,(SameQ[Union[#],#]&/@Sort/@(And@@DifferenceTable[l]))
]

Timings

CostasQ[l_List]:=And@@(SameQ[Union[#],#]&/@Sort/@DifferenceTable[l])

Count[Permutations[Range[#]],_?CostasQ]&/@Range[8]//Timing

CostasQ[l_List]:=And@@(SameQ[Union[#],#]&/@Sort/@DifferenceTable[l]) /; Length[l]==2
CostasQ[l_List]:=(SameQ[Union[#],#]&/@Sort/@(And@@DifferenceTable[l]))

Count[Permutations[Range[#]],_?CostasQ]&/@Range[8]//Timing

Examples

DifferenceTable[{0,1,4,9,15,22,32,34}]

CostasQ[{1,2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10}]

Sort/@LevelLists[{1,2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10}]

Select[Permutations[Range[1]],CostasQ]

Select[Permutations[Range[2]],CostasQ]

Select[Permutations[Range[3]],CostasQ]

Select[Permutations[Range[4]],CostasQ]

Select[Permutations[Range[5]],CostasQ]

DifferenceTable[{1,3,4,2,5}]

Count[Permutations[Range[#]],_?CostasQ]&/@Range[9]//Timing

Count[Permutations[Range[#]],_?CostasQ]&/@Range[10]//Timing

Count[Permutations[Range[#]],_?CostasQ]&/@Range[11]//Timing

Canonical

CanonicalQ[l_List]:=First[l]<Last[l]

Select[Permutations[Range[4]],CostasQ[#]&&CanonicalQ[#]&]

Canonicalize[l_]:=First[Sort[NestList[RotateLeft,l,Length[l]-1]]]

Canonicalize/@%34

OrderedQ/@%34

Count[Union[Canonicalize/@Permutations[Range[#]]],_?(CanonicalQ[#]&&CostasQ[#]&)]&/@Range[8]//Timing

Figure

Graphics[{AbsolutePointSize[5],Point/@MapIndexed[{#1,#2[[1]]}&,{11,10,4,24,7,23,3,18,21,9,26,16,5,1,15,27,2,25,17,22,19,6,8,12,20,13,14}]},GridLines->{Range[0,27],Range[0,27]},PlotRange->{{1-.2,27.2},{1-.2,27.2}},ImageSize->300]

Length[{11,10,4,24,7,23,3,18,21,9,26,16,5,1,15,27,2,25,17,22,19,6,8,12,20,13,14}]