C Count lacings of a shoe with two rows of N eyelets C subjected to the "physical" condition that all C eyelets are "loaded", i.e. that there is a force C component towards the opposite eyelet column. C C Author: Hugo Pfoertner http://www.pfoertner.org/ C C Version history: C 28.12.2002 Mark symmetric lacings in output C 18.12.2002 Modified condition to exclude unloaded eyelets, C count symmetric configs, link to NEXPER C 17.12.2002 Initial version C C N has to be modified here to create sequence entries PARAMETER (N=5, N2=N+N, M=N2-2, N2P=N2+1) INTEGER E(N2), EE(N,2), A(M) LOGICAL EVEN, NEXT INTEGER L, LOVER CHARACTER*1 SYMM EQUIVALENCE (E,EE) C C SUBROUTINE TO GENERATE ALL PERMUTATIONS EXTERNAL NEXPER C C FIXED START AND END EE(1,1) = 1 EE(N,2) = N2 C COUNTER FOR LACINGS THAT CONFORM WITH CONDITIONS L = 0 C COUNTER FOR SYMMETRIC CONFIGS LS = 0 C OVERFLOW COUNTER IF L EXCEEDS 1E9 (TOTAL COUNT LOVER*1E9 + L) LOVER = 0 C CREATE PERMUTATIONS, STATUS NEXT = .FALSE. C C START OF LOOP OVER PERMUTATIONS CREATED BY CALLING NEXPER C 10 CONTINUE C C The source code for NEXPER is available from C http://www.cs.sunysb.edu/~algorith/implement/wilf/distrib/processed/nexper_2.f C It is also part of N.J.A. Sloane's program provided in a link in C OEIS A078602: C http://www.research.att.com/~njas/sequences/a078602.txt C CALL NEXPER ( M, A, NEXT, EVEN ) C C SOMETIMES NEXPER DOESN'T CHANGE "NEXT" AFTER CYCLING THROUGH C ALL PERMUTATIONS, BUT OVERWRITES A(1) WITH ZERO IF ( A(1) .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 AT LEAST ONE OF THE DIRECTLY CONNECTED C EYELETS IS ON THE OPPOSITE SIDE DO 30 I = 2, N2-1 C IF ( (E(I-1) .LE. N .AND. E(I) .LE. N .AND. E(I+1) .LE. N) C & .OR.(E(I-1) .GT. N .AND. E(I) .GT. N .AND. E(I+1) .GT. N)) C & GOTO 10 C REPLACED BY THE FOLLOWING, PROBABLY MORE EFFICIENT CONDITIONS IF ( E(I) .LE. N ) THEN C CHECK IF ONE OF THE CONNECTED NEIGHBORS LIES ON OPPOSITE SIDE 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 C UNLOADED EYELET FOUND, DISREGARD PATH GOTO 10 30 CONTINUE C COUNT LACINGS L = L + 1 C OVERFLOW PROTECTION TO AVOID 32BIT INTEGER OVERFLOW IF ( L .GT. 1000000000 ) THEN L = L - 1000000000 LOVER = LOVER + 1 WRITE (*,*) ' L OVERFLOW: ', LOVER ENDIF C CHECK FOR SYMMETRIC CONFIG SYMM = ' ' DO 50 I = 2, N IF ( E(I) .NE. N2P-E(N2P-I) ) GOTO 60 50 CONTINUE SYMM = 'S' LS = LS + 1 60 CONTINUE C TO PRINT RESULTS ACTIVATE COMMENTED LINES WRITE (*,1000) SYMM, L, (E(I),I=1,N2) 1000 FORMAT (A, I6, 2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3,:,2I3) IF ( NEXT ) GOTO 10 C 200 CONTINUE IF ( LOVER .EQ. 0 ) THEN WRITE (*,1001) N, L, LS, LS+(L-LS)/2 ELSE WRITE (*,1002) N, L, LOVER, LS ENDIF 1001 FORMAT ( ' N=', I2, ', L=',I10 ,', LSYM=', I8, ', LUNDIR:', I9) 1002 FORMAT ( ' N=', I2, ', L=', I10,' +',I3,'*10^9, LSYM=', I9 ) END ------------------------------------------------------ Results: (symmetric lacings are marked with "S") N=2 1 o o 4 2 o o 3 S 1 1 2 3 4 S 2 1 3 2 4 N= 2, L= 2, LSYM= 2, LUNDIR: 2 N=3 1 o o 6 2 o o 5 3 o o 4 1 1 4 2 3 5 6 S 2 1 2 4 3 5 6 3 1 3 4 2 5 6 4 1 4 3 2 5 6 5 1 5 3 2 4 6 S 6 1 3 5 2 4 6 7 1 2 5 3 4 6 8 1 5 2 3 4 6 9 1 2 4 5 3 6 S 10 1 4 2 5 3 6 11 1 5 2 4 3 6 12 1 2 5 4 3 6 S 13 1 4 5 2 3 6 14 1 5 4 2 3 6 S 15 1 5 4 3 2 6 16 1 4 5 3 2 6 17 1 3 5 4 2 6 S 18 1 5 3 4 2 6 19 1 4 3 5 2 6 20 1 3 4 5 2 6 N= 3, L= 20, LSYM= 6, LUNDIR: 13 N=4 1 o o 8 2 o o 7 3 o o 6 4 o o 5 1 1 5 2 3 6 4 7 8 S 2 1 2 5 3 6 4 7 8 3 1 3 5 2 6 4 7 8 4 1 5 3 2 6 4 7 8 5 1 6 3 2 5 4 7 8 6 1 3 6 2 5 4 7 8 7 1 2 6 3 5 4 7 8 8 1 6 2 3 5 4 7 8 S 9 1 2 5 6 3 4 7 8 10 1 5 2 6 3 4 7 8 11 1 6 2 5 3 4 7 8 12 1 2 6 5 3 4 7 8 13 1 3 6 5 2 4 7 8 14 1 6 3 5 2 4 7 8 15 1 5 3 6 2 4 7 8 16 1 3 5 6 2 4 7 8 17 1 4 5 6 2 3 7 8 18 1 5 4 6 2 3 7 8 19 1 6 4 5 2 3 7 8 20 1 4 6 5 2 3 7 8 S 21 1 2 6 5 4 3 7 8 22 1 6 2 5 4 3 7 8 23 1 5 2 6 4 3 7 8 24 1 2 5 6 4 3 7 8 25 1 6 2 4 5 3 7 8 S 26 1 2 6 4 5 3 7 8 27 1 4 6 2 5 3 7 8 28 1 6 4 2 5 3 7 8 29 1 5 4 2 6 3 7 8 30 1 4 5 2 6 3 7 8 31 1 2 5 4 6 3 7 8 32 1 5 2 4 6 3 7 8 33 1 5 3 4 6 2 7 8 34 1 3 5 4 6 2 7 8 35 1 4 5 3 6 2 7 8 36 1 5 4 3 6 2 7 8 37 1 6 4 3 5 2 7 8 38 1 4 6 3 5 2 7 8 39 1 3 6 4 5 2 7 8 40 1 6 3 4 5 2 7 8 41 1 3 5 6 4 2 7 8 42 1 5 3 6 4 2 7 8 43 1 6 3 5 4 2 7 8 44 1 3 6 5 4 2 7 8 45 1 4 6 5 3 2 7 8 46 1 6 4 5 3 2 7 8 47 1 5 4 6 3 2 7 8 48 1 4 5 6 3 2 7 8 49 1 4 5 7 3 2 6 8 50 1 5 4 7 3 2 6 8 51 1 7 4 5 3 2 6 8 52 1 4 7 5 3 2 6 8 S 53 1 3 7 5 4 2 6 8 54 1 7 3 5 4 2 6 8 55 1 5 3 7 4 2 6 8 56 1 3 5 7 4 2 6 8 57 1 7 3 4 5 2 6 8 S 58 1 3 7 4 5 2 6 8 59 1 4 7 3 5 2 6 8 60 1 7 4 3 5 2 6 8 61 1 5 4 3 7 2 6 8 62 1 4 5 3 7 2 6 8 63 1 3 5 4 7 2 6 8 64 1 5 3 4 7 2 6 8 65 1 5 2 4 7 3 6 8 66 1 2 5 4 7 3 6 8 67 1 4 5 2 7 3 6 8 68 1 5 4 2 7 3 6 8 69 1 7 4 2 5 3 6 8 70 1 4 7 2 5 3 6 8 71 1 2 7 4 5 3 6 8 72 1 7 2 4 5 3 6 8 73 1 2 5 7 4 3 6 8 74 1 5 2 7 4 3 6 8 75 1 7 2 5 4 3 6 8 76 1 2 7 5 4 3 6 8 77 1 4 7 5 2 3 6 8 78 1 7 4 5 2 3 6 8 79 1 5 4 7 2 3 6 8 80 1 4 5 7 2 3 6 8 S 81 1 3 5 7 2 4 6 8 82 1 5 3 7 2 4 6 8 83 1 7 3 5 2 4 6 8 84 1 3 7 5 2 4 6 8 85 1 2 7 5 3 4 6 8 86 1 7 2 5 3 4 6 8 87 1 5 2 7 3 4 6 8 88 1 2 5 7 3 4 6 8 89 1 7 2 3 5 4 6 8 90 1 2 7 3 5 4 6 8 91 1 3 7 2 5 4 6 8 92 1 7 3 2 5 4 6 8 93 1 5 3 2 7 4 6 8 S 94 1 3 5 2 7 4 6 8 95 1 2 5 3 7 4 6 8 96 1 5 2 3 7 4 6 8 97 1 6 2 3 7 4 5 8 98 1 2 6 3 7 4 5 8 99 1 3 6 2 7 4 5 8 100 1 6 3 2 7 4 5 8 101 1 7 3 2 6 4 5 8 102 1 3 7 2 6 4 5 8 103 1 2 7 3 6 4 5 8 104 1 7 2 3 6 4 5 8 105 1 2 6 7 3 4 5 8 106 1 6 2 7 3 4 5 8 107 1 7 2 6 3 4 5 8 108 1 2 7 6 3 4 5 8 109 1 3 7 6 2 4 5 8 110 1 7 3 6 2 4 5 8 111 1 6 3 7 2 4 5 8 112 1 3 6 7 2 4 5 8 S 113 1 4 6 7 2 3 5 8 114 1 6 4 7 2 3 5 8 115 1 7 4 6 2 3 5 8 116 1 4 7 6 2 3 5 8 117 1 2 7 6 4 3 5 8 118 1 7 2 6 4 3 5 8 119 1 6 2 7 4 3 5 8 120 1 2 6 7 4 3 5 8 121 1 7 2 4 6 3 5 8 122 1 2 7 4 6 3 5 8 123 1 4 7 2 6 3 5 8 124 1 7 4 2 6 3 5 8 125 1 6 4 2 7 3 5 8 S 126 1 4 6 2 7 3 5 8 127 1 2 6 4 7 3 5 8 128 1 6 2 4 7 3 5 8 129 1 6 3 4 7 2 5 8 130 1 3 6 4 7 2 5 8 131 1 4 6 3 7 2 5 8 132 1 6 4 3 7 2 5 8 133 1 7 4 3 6 2 5 8 S 134 1 4 7 3 6 2 5 8 135 1 3 7 4 6 2 5 8 136 1 7 3 4 6 2 5 8 137 1 3 6 7 4 2 5 8 138 1 6 3 7 4 2 5 8 139 1 7 3 6 4 2 5 8 140 1 3 7 6 4 2 5 8 S 141 1 4 7 6 3 2 5 8 142 1 7 4 6 3 2 5 8 143 1 6 4 7 3 2 5 8 144 1 4 6 7 3 2 5 8 145 1 7 6 3 5 2 4 8 146 1 6 7 3 5 2 4 8 147 1 7 3 6 5 2 4 8 148 1 6 3 7 5 2 4 8 149 1 5 3 7 6 2 4 8 150 1 7 3 5 6 2 4 8 S 151 1 5 7 3 6 2 4 8 152 1 7 5 3 6 2 4 8 153 1 6 5 3 7 2 4 8 154 1 5 6 3 7 2 4 8 155 1 6 3 5 7 2 4 8 156 1 5 3 6 7 2 4 8 157 1 5 2 6 7 3 4 8 158 1 6 2 5 7 3 4 8 S 159 1 5 6 2 7 3 4 8 160 1 6 5 2 7 3 4 8 161 1 7 5 2 6 3 4 8 162 1 5 7 2 6 3 4 8 163 1 7 2 5 6 3 4 8 164 1 5 2 7 6 3 4 8 165 1 6 2 7 5 3 4 8 166 1 7 2 6 5 3 4 8 167 1 6 7 2 5 3 4 8 168 1 7 6 2 5 3 4 8 169 1 3 6 7 2 5 4 8 170 1 6 3 7 2 5 4 8 171 1 7 3 6 2 5 4 8 172 1 3 7 6 2 5 4 8 173 1 6 7 3 2 5 4 8 174 1 7 6 3 2 5 4 8 175 1 7 6 2 3 5 4 8 176 1 6 7 2 3 5 4 8 177 1 2 7 6 3 5 4 8 178 1 7 2 6 3 5 4 8 179 1 6 2 7 3 5 4 8 180 1 2 6 7 3 5 4 8 181 1 7 2 3 6 5 4 8 182 1 2 7 3 6 5 4 8 183 1 3 7 2 6 5 4 8 184 1 7 3 2 6 5 4 8 185 1 6 3 2 7 5 4 8 186 1 3 6 2 7 5 4 8 187 1 2 6 3 7 5 4 8 188 1 6 2 3 7 5 4 8 189 1 5 2 3 7 6 4 8 190 1 2 5 3 7 6 4 8 191 1 3 5 2 7 6 4 8 S 192 1 5 3 2 7 6 4 8 193 1 7 3 2 5 6 4 8 194 1 3 7 2 5 6 4 8 195 1 2 7 3 5 6 4 8 196 1 7 2 3 5 6 4 8 197 1 2 5 7 3 6 4 8 198 1 5 2 7 3 6 4 8 199 1 7 2 5 3 6 4 8 200 1 2 7 5 3 6 4 8 201 1 5 7 2 3 6 4 8 202 1 7 5 2 3 6 4 8 203 1 7 5 3 2 6 4 8 204 1 5 7 3 2 6 4 8 205 1 3 7 5 2 6 4 8 206 1 7 3 5 2 6 4 8 S 207 1 5 3 7 2 6 4 8 208 1 3 5 7 2 6 4 8 209 1 3 5 6 2 7 4 8 210 1 5 3 6 2 7 4 8 211 1 6 3 5 2 7 4 8 212 1 3 6 5 2 7 4 8 213 1 5 6 3 2 7 4 8 214 1 6 5 3 2 7 4 8 215 1 6 5 2 3 7 4 8 216 1 5 6 2 3 7 4 8 217 1 2 6 5 3 7 4 8 218 1 6 2 5 3 7 4 8 S 219 1 5 2 6 3 7 4 8 220 1 2 5 6 3 7 4 8 221 1 6 2 3 5 7 4 8 222 1 2 6 3 5 7 4 8 223 1 3 6 2 5 7 4 8 224 1 6 3 2 5 7 4 8 225 1 5 3 2 6 7 4 8 226 1 3 5 2 6 7 4 8 227 1 2 5 3 6 7 4 8 S 228 1 5 2 3 6 7 4 8 229 1 5 2 4 6 7 3 8 230 1 2 5 4 6 7 3 8 231 1 4 5 2 6 7 3 8 232 1 5 4 2 6 7 3 8 233 1 6 4 2 5 7 3 8 234 1 4 6 2 5 7 3 8 235 1 2 6 4 5 7 3 8 S 236 1 6 2 4 5 7 3 8 237 1 2 5 6 4 7 3 8 238 1 5 2 6 4 7 3 8 S 239 1 6 2 5 4 7 3 8 240 1 2 6 5 4 7 3 8 241 1 5 6 2 4 7 3 8 242 1 6 5 2 4 7 3 8 243 1 6 5 4 2 7 3 8 244 1 5 6 4 2 7 3 8 245 1 4 6 5 2 7 3 8 246 1 6 4 5 2 7 3 8 247 1 5 4 6 2 7 3 8 248 1 4 5 6 2 7 3 8 249 1 4 5 7 2 6 3 8 250 1 5 4 7 2 6 3 8 251 1 7 4 5 2 6 3 8 252 1 4 7 5 2 6 3 8 253 1 5 7 4 2 6 3 8 254 1 7 5 4 2 6 3 8 255 1 7 5 2 4 6 3 8 256 1 5 7 2 4 6 3 8 257 1 2 7 5 4 6 3 8 258 1 7 2 5 4 6 3 8 259 1 5 2 7 4 6 3 8 260 1 2 5 7 4 6 3 8 261 1 7 2 4 5 6 3 8 262 1 2 7 4 5 6 3 8 263 1 4 7 2 5 6 3 8 264 1 7 4 2 5 6 3 8 265 1 5 4 2 7 6 3 8 266 1 4 5 2 7 6 3 8 267 1 2 5 4 7 6 3 8 268 1 5 2 4 7 6 3 8 269 1 6 2 4 7 5 3 8 270 1 2 6 4 7 5 3 8 271 1 4 6 2 7 5 3 8 S 272 1 6 4 2 7 5 3 8 273 1 7 4 2 6 5 3 8 274 1 4 7 2 6 5 3 8 275 1 2 7 4 6 5 3 8 276 1 7 2 4 6 5 3 8 277 1 2 6 7 4 5 3 8 278 1 6 2 7 4 5 3 8 279 1 7 2 6 4 5 3 8 280 1 2 7 6 4 5 3 8 281 1 6 7 2 4 5 3 8 282 1 7 6 2 4 5 3 8 283 1 7 6 4 2 5 3 8 284 1 6 7 4 2 5 3 8 285 1 4 7 6 2 5 3 8 286 1 7 4 6 2 5 3 8 S 287 1 6 4 7 2 5 3 8 288 1 4 6 7 2 5 3 8 289 1 7 6 2 5 4 3 8 290 1 6 7 2 5 4 3 8 291 1 7 2 6 5 4 3 8 292 1 6 2 7 5 4 3 8 293 1 5 2 7 6 4 3 8 294 1 7 2 5 6 4 3 8 295 1 5 7 2 6 4 3 8 296 1 7 5 2 6 4 3 8 S 297 1 6 5 2 7 4 3 8 298 1 5 6 2 7 4 3 8 299 1 6 2 5 7 4 3 8 300 1 5 2 6 7 4 3 8 301 1 5 4 6 7 2 3 8 302 1 6 4 5 7 2 3 8 303 1 5 6 4 7 2 3 8 304 1 6 5 4 7 2 3 8 305 1 7 5 4 6 2 3 8 306 1 5 7 4 6 2 3 8 307 1 7 4 5 6 2 3 8 308 1 5 4 7 6 2 3 8 309 1 6 4 7 5 2 3 8 310 1 7 4 6 5 2 3 8 S 311 1 6 7 4 5 2 3 8 312 1 7 6 4 5 2 3 8 S 313 1 7 6 4 5 3 2 8 314 1 6 7 4 5 3 2 8 315 1 7 4 6 5 3 2 8 316 1 6 4 7 5 3 2 8 317 1 5 4 7 6 3 2 8 318 1 7 4 5 6 3 2 8 319 1 5 7 4 6 3 2 8 320 1 7 5 4 6 3 2 8 321 1 6 5 4 7 3 2 8 322 1 5 6 4 7 3 2 8 323 1 6 4 5 7 3 2 8 324 1 5 4 6 7 3 2 8 325 1 5 3 6 7 4 2 8 326 1 6 3 5 7 4 2 8 327 1 5 6 3 7 4 2 8 328 1 6 5 3 7 4 2 8 S 329 1 7 5 3 6 4 2 8 330 1 5 7 3 6 4 2 8 331 1 7 3 5 6 4 2 8 332 1 5 3 7 6 4 2 8 333 1 6 3 7 5 4 2 8 334 1 7 3 6 5 4 2 8 335 1 6 7 3 5 4 2 8 336 1 7 6 3 5 4 2 8 337 1 4 6 7 3 5 2 8 338 1 6 4 7 3 5 2 8 S 339 1 7 4 6 3 5 2 8 340 1 4 7 6 3 5 2 8 341 1 6 7 4 3 5 2 8 342 1 7 6 4 3 5 2 8 343 1 7 6 3 4 5 2 8 344 1 6 7 3 4 5 2 8 345 1 3 7 6 4 5 2 8 346 1 7 3 6 4 5 2 8 347 1 6 3 7 4 5 2 8 348 1 3 6 7 4 5 2 8 349 1 7 3 4 6 5 2 8 350 1 3 7 4 6 5 2 8 351 1 4 7 3 6 5 2 8 S 352 1 7 4 3 6 5 2 8 353 1 6 4 3 7 5 2 8 354 1 4 6 3 7 5 2 8 355 1 3 6 4 7 5 2 8 356 1 6 3 4 7 5 2 8 357 1 5 3 4 7 6 2 8 358 1 3 5 4 7 6 2 8 359 1 4 5 3 7 6 2 8 360 1 5 4 3 7 6 2 8 361 1 7 4 3 5 6 2 8 362 1 4 7 3 5 6 2 8 363 1 3 7 4 5 6 2 8 S 364 1 7 3 4 5 6 2 8 365 1 3 5 7 4 6 2 8 366 1 5 3 7 4 6 2 8 S 367 1 7 3 5 4 6 2 8 368 1 3 7 5 4 6 2 8 369 1 5 7 3 4 6 2 8 370 1 7 5 3 4 6 2 8 371 1 7 5 4 3 6 2 8 372 1 5 7 4 3 6 2 8 373 1 4 7 5 3 6 2 8 374 1 7 4 5 3 6 2 8 375 1 5 4 7 3 6 2 8 376 1 4 5 7 3 6 2 8 377 1 4 5 6 3 7 2 8 378 1 5 4 6 3 7 2 8 379 1 6 4 5 3 7 2 8 380 1 4 6 5 3 7 2 8 381 1 5 6 4 3 7 2 8 382 1 6 5 4 3 7 2 8 383 1 6 5 3 4 7 2 8 384 1 5 6 3 4 7 2 8 385 1 3 6 5 4 7 2 8 386 1 6 3 5 4 7 2 8 387 1 5 3 6 4 7 2 8 388 1 3 5 6 4 7 2 8 389 1 6 3 4 5 7 2 8 390 1 3 6 4 5 7 2 8 391 1 4 6 3 5 7 2 8 392 1 6 4 3 5 7 2 8 393 1 5 4 3 6 7 2 8 394 1 4 5 3 6 7 2 8 395 1 3 5 4 6 7 2 8 396 1 5 3 4 6 7 2 8 N= 4, L= 396, LSYM= 30, LUNDIR: 213