# Note: This Maple worksheet is supposed to give a simple implementation, not an efficient one! It is intended to be read as an introduction to the topic of complete and optimal rulers. An efficient Java-implementation can be found on here.

with(combstruct):

# Compute the complete rulers with S segments and length L. If the PrintFlag is true, the generated rulers will be printed.  Returns the number of rulers with S segments and length L.

CompleteRuler := proc(S, L, PrintFlag) 
option remember; local C, R, n, D2R, isComplete;

# Converts a difference representation to a ruler representation.

D2R := proc(L) local i, j;
[0, seq(add(L[j],j = 1..i), i = 1..nops(L))] end;

# Test if a ruler is complete.

isComplete := proc(R) local S, i, j;
S := {};
for i from nops(R) by -1 to 1 do
   for j from 1 to i-1 do
      S := S union {R[i]-R[i-j]};
   od;
od:
nops(S) = R[nops(R)] end:

# We need 'combstruct' for 'iterstructs' and 'nextstruct'. Composition of a positive integer L into positive integers with S parts of size at least 1, where the order of  summands is important.

C := iterstructs(Composition(L), size=S):
n := 0;
while not finished(C) do
   R := D2R(nextstruct(C));
   if isComplete(R) 
   then if(PrintFlag) then print(R) fi; 
   n := n + 1 fi;
od;
n end:

# Generate all complete rulers with length 13 and 5 segments.

CompleteRuler(5, 13, true);

[0, 3, 7, 11, 12, 13] [0, 2, 8, 9, 12, 13] [0, 2, 4, 7, 12, 13]
[0, 1, 6, 9, 11, 13] [0, 1, 4, 5, 11, 13] [0, 1, 2, 6, 10, 13]

PerfectRuler := proc(L) 
local i, c;
i := 0: 
do i := i +1;
   c := CompleteRuler(i, L, false);
   if(c <> 0) then break fi;
od;
c end:

# Compute the sequence A103300 of OEIS!

seq(PerfectRuler(i), i = 1..13);

1, 1, 2, 3, 4, 2, 12, 8, 4, 38, 30, 14, 6

# Compute the number of segments of a ruler with length L. Note: The following function is almost identical to 'PerfectRuler', the only difference is the value returned!

LengthToSegment := proc(L) 
local i, c;
i := 0: 
do i := i +1;
   c := CompleteRuler(i, L, false);
   if(c <> 0) then break fi;
od;
i end:

# A103298 on OEIS

seq(LengthToSegment(i), i = 1..13);

1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5

# Now we can also compute sequence A004137 of OEIS, which gives the perfect rulers which are optimal simply by noting the indices where the values increase!

OptimalRulers := proc(UpTo) 
local T, U, i, s, c;
T := [0,seq(LengthToSegment(i), i = 1..(UpTo+1))];
U := []; s := 0; c := 0;
for i from 1 to nops(T) do
   if c <> T[i] then
      s := s + c; 
      c := T[i]; 
      U := [op(U), i-2];
   fi;
od;
U end:

# "That sequence is a hard one, it means that a computer  program will have either hard time to get the next term OR the definition makes it difficult to program easily." From an email by Simon Plouffe to the author. So please have a little patience!

# A004137 on OEIS

OptimalRulers(17);

[ 1, 3, 6, 9, 13, 17]

# The function CompleteRuler(S, L) is depending on the length L and the number of segments S. Indeed, it generates following triangle of numbers:

for i from 1 to 17 do
   seq(CompleteRuler(k, i, false),k = 1..i);
od; 

1
0, 1
0, 2, 1
0, 0, 3, 1
0, 0, 4, 4,  1
0, 0, 2, 9,  5,  1
0, 0, 0,12, 14,  6,   1
0, 0, 0, 8, 27,  20,  7,    1
0, 0, 0, 4, 40,  48, 27,    8,     1
0, 0, 0, 0, 38,  90, 75,   35,     9,    1
0, 0, 0, 0, 30, 134, 166, 110,    44,   10,    1
0, 0, 0, 0, 14, 166, 311, 277,   154,   54,   11,    1
0, 0, 0, 0,  6, 166, 490, 590,   431,  208,   65,   12,    1
0, 0, 0, 0,  0, 130, 660, 1096, 1022,  639,  273,   77,   13,  1
0, 0, 0, 0,  0,  80, 800, 1816, 2132, 1662,  912,  350,   90,  14,   1
0, 0, 0, 0,  0,  32, 790, 2641, 3980, 3796, 2574, 1262,  440, 104,  15,  1
0, 0, 0, 0,  0,  12, 710, 3476, 6721, 7796, 6371, 3836, 1702, 544, 119, 16, 1

# This is the sequence A103294 of OEIS.

back

2005-01-05