1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #!/usr/local/bin/perl # Uses Roy O. Davies pattern to generate a single Langford chain for given n. # # John Miller, Feb 1997 $n = $ARGV [0]; if ( $n < 8 ) { exit ;} # otherwise program degenerates if ( ! ( $n %4 || ( $n +1) %4 ) ) { exit ;} # n must be a multiple of 4 or one less. $even = $n % 2 == 0; $odd = $n % 2 == 1; $m = $odd ? ( $n +1)/4 : $n /4; # m is the basis for patterns below $mm = 2* $n ; $i = 0; # i$ will be incremented in the gen & add routines. gen (4* $m -4, 2* $m ); add (4* $m -2); gen (2* $m -3, 1); add (4* $m -1); gen (1, 2* $m -3); gen (2* $m , 4* $m -4); if ( $odd ) { add (2* $m -1); } # 2m-1 goes in the middle if ( $even ) { add (4* $m ); } # one n goes in the middle gen (4* $m -3, 2* $m +1); add (4* $m -2); gen (2* $m -2, 2); add (2* $m -1); # this 2m-1 always here add (4* $m -1); gen (2, 2* $m -2); gen (2* $m +1, 4* $m -3); if ( $even ) { add (2* $m -1); # 2m-1 goes to the end add (4* $m ); # the other n at the end } #print the arrangement #===================== #for ($i=1; $i<=$mm; $i++) { print " $L[$i]";} print "\n"; #check for correctness, but destroy in the process for ( $p =1; $p <= $mm ; $p ++) { $k = $L [ $p ]; if ( $k == 0) { next } if ( $L [ $p + $k +1] != $k ) { die }; $L [ $p + $k +1] = 0; } print "checks out OK!\n" ; exit ; # add a sequence of odd or even numbers to L sub gen { ( $a , $b ) = @_ ; # range is passed in argument list. if ( $a < $b ) { for ( $k = $a ; $k <= $b ; $k +=2) { $L [++ $i ] = $k ; }} if ( $a > $b ) { for ( $k = $a ; $k >= $b ; $k -=2) { $L [++ $i ] = $k ; }} } #add a single number to L sub add { ( $a ) = @_ ; $L [++ $i ] = $a ; } |