C Count lacings of a shoe with two columns of N eyelets C subjected to the condition that there is NO direct C "horizontal" connection between any adjacent eyelet C pair (e.g. 2<->2*n-1, 3<->2*n-2, 4<->2*n-3,....) C C Author: Hugo Pfoertner http:/www.pfoertner.org/ C C Version history: C 17.01.2003 Non-straight lacings C 14.01.2003 Horizontal connection configs (straight lacings) C 05.01.2003 NEXPER replaced by LPG C 03.01.2003 Count crossing-free lacings (OEIS sequence A079410) C 17.12.2002 Initial version C C N is the number of eyelets in one row. C N=8 takes approx 1 day CPU time on an Intel PIII 550MHz, C ((2*8-2)!=14! configs to check) C N=9 is expected to run approx 15*16=240 days on the same CPU. C PARAMETER (N=8, N2=N+N, M=N2-2, N2P=N2+1, N2M=N2-1) PARAMETER (NN=N*N+N*N) INTEGER E(N2), EE(N,2), A(M) INTEGER*8 L EQUIVALENCE (E,EE) C C FIXED START AND END EE(1,1) = 1 EE(N,2) = N2 C PRESET PERMUTATION ARRAY DO 2 I = 1, M A(I) = I 2 CONTINUE C STATUS OF PERMUTATION GENERATION NEXT = -1 C COUNTER FOR LEGAL LACINGS L = 0 C WRITE (*,1003) N 1003 FORMAT ( ' N =', I2, // , ' Non-Straight Lacings', / ) C 10 CONTINUE C CREATE NEXT PERMUTATION IF ( NEXT .EQ. -1 ) THEN NEXT = 1 ELSE C Create permutations in lexicographic order CALL LPG ( M, A, NEXT ) ENDIF IF ( NEXT .EQ. 0 ) GOTO 200 C INSERT PERMUTED PATH BETWEEN FIXED START AND END DO 20 I = 1, M E(I+1) = A(I) + 1 20 CONTINUE C TEST CONDITION THAT THERE IS NO STRAIGHT CONNECTION C TO THE CORRESPONDING EYELET ON THE OPPOSITE SIDE DO 30 I = 2, N2M IF ( E(I) .EQ. N2P-E(I-1) ) GOTO 10 IF ( E(I) .EQ. N2P-E(I+1) ) GOTO 10 C AT LEAST ONE CONNECTION TO OPPOSITE SIDE REQUIRED IF ( E(I) .LE. N ) THEN IF ( E(I-1) .GT. N ) GOTO 30 IF ( E(I+1) .GT. N ) GOTO 30 ELSE IF ( E(I-1) .LE. N ) GOTO 30 IF ( E(I+1) .LE. N ) GOTO 30 ENDIF GOTO 10 30 CONTINUE C C COUNT LACINGS L = L + 1 C...+....1....+....2....+....3....+....4....+....5....+....6....+....7.. C TO PRINT RESULTS ACTIVATE COMMENTED LINES C WRITE (*,1000) L, (E(I),I=1,N2) C1000 FORMAT (I6, 2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3) C SKIP BACK TO NEXT PERMUTATION GOTO 10 C 200 CONTINUE C PRINT RESULTS WRITE (*,1001) N, L, L/2 1001 FORMAT ( ' N=', I2, ', L=', I12,', LUNDIR:', I11) END ....+....1....+....2....+....3....+....4....+....5....+....6....+....7.. Results for N=3 and N=4 N = 3 Non-Straight Lacings 1 1 2 4 5 3 6 2 1 3 5 4 2 6 3 1 4 2 3 5 6 4 1 4 5 3 2 6 5 1 5 3 2 4 6 6 1 5 4 2 3 6 N= 3, L= 6, LUNDIR: 3 ....+....1....+....2....+....3....+....4....+....5....+....6....+....7.. N = 4 Non-Straight Lacings 1 1 2 5 3 7 4 6 8 2 1 2 5 3 7 6 4 8 3 1 2 5 6 4 3 7 8 4 1 2 5 6 4 7 3 8 5 1 2 5 7 3 4 6 8 6 1 2 6 4 7 3 5 8 7 1 2 6 4 7 5 3 8 8 1 2 6 5 3 4 7 8 9 1 2 6 5 3 7 4 8 10 1 2 6 7 4 3 5 8 11 1 3 5 2 6 4 7 8 12 1 3 5 2 6 7 4 8 13 1 3 5 6 2 4 7 8 14 1 3 5 7 4 2 6 8 15 1 3 5 7 4 6 2 8 16 1 3 7 4 6 2 5 8 17 1 3 7 4 6 5 2 8 18 1 3 7 5 2 4 6 8 19 1 3 7 5 2 6 4 8 20 1 3 7 6 4 2 5 8 21 1 4 6 2 5 3 7 8 22 1 4 6 2 5 7 3 8 23 1 4 6 5 2 3 7 8 24 1 4 6 7 3 2 5 8 25 1 4 6 7 3 5 2 8 26 1 4 7 3 5 2 6 8 27 1 4 7 3 5 6 2 8 28 1 4 7 5 3 2 6 8 29 1 4 7 6 2 3 5 8 30 1 4 7 6 2 5 3 8 31 1 5 2 3 7 4 6 8 32 1 5 2 3 7 6 4 8 33 1 5 2 4 6 7 3 8 34 1 5 2 6 4 3 7 8 35 1 5 2 6 4 7 3 8 36 1 5 2 6 7 3 4 8 37 1 5 2 6 7 4 3 8 38 1 5 3 2 6 4 7 8 39 1 5 3 2 6 7 4 8 40 1 5 3 4 7 6 2 8 41 1 5 3 7 4 2 6 8 42 1 5 3 7 4 6 2 8 43 1 5 3 7 6 2 4 8 44 1 5 3 7 6 4 2 8 45 1 5 6 2 3 7 4 8 46 1 5 6 2 4 7 3 8 47 1 5 6 4 7 3 2 8 48 1 5 7 3 2 6 4 8 49 1 5 7 3 4 6 2 8 50 1 5 7 4 6 2 3 8 51 1 6 2 3 5 7 4 8 52 1 6 2 4 7 3 5 8 53 1 6 2 4 7 5 3 8 54 1 6 2 5 3 4 7 8 55 1 6 2 5 3 7 4 8 56 1 6 2 5 7 3 4 8 57 1 6 2 5 7 4 3 8 58 1 6 4 2 5 3 7 8 59 1 6 4 2 5 7 3 8 60 1 6 4 3 7 5 2 8 61 1 6 4 7 3 2 5 8 62 1 6 4 7 3 5 2 8 63 1 6 4 7 5 2 3 8 64 1 6 4 7 5 3 2 8 65 1 6 5 2 3 7 4 8 66 1 6 5 2 4 7 3 8 67 1 6 5 3 7 4 2 8 68 1 6 7 3 5 2 4 8 69 1 6 7 4 2 5 3 8 70 1 6 7 4 3 5 2 8 71 1 7 3 2 5 6 4 8 72 1 7 3 4 6 2 5 8 73 1 7 3 4 6 5 2 8 74 1 7 3 5 2 4 6 8 75 1 7 3 5 2 6 4 8 76 1 7 3 5 6 2 4 8 77 1 7 3 5 6 4 2 8 78 1 7 4 2 6 5 3 8 79 1 7 4 3 5 2 6 8 80 1 7 4 3 5 6 2 8 81 1 7 4 6 2 3 5 8 82 1 7 4 6 2 5 3 8 83 1 7 4 6 5 2 3 8 84 1 7 4 6 5 3 2 8 85 1 7 5 2 6 4 3 8 86 1 7 5 3 2 6 4 8 87 1 7 5 3 4 6 2 8 88 1 7 6 2 5 3 4 8 89 1 7 6 4 2 5 3 8 90 1 7 6 4 3 5 2 8 N= 4, L= 90, LUNDIR: 45