This site is supported by donations to The OEIS Foundation.
Complete non-self-intersecting paths
This is the Contents
Complete non-self-intersecting paths in bounded square and cubic lattices
Chris Gribble is currently working on this topic.
Introduction
I have computed all complete non-self-intersecting paths (CNSIPs) in square and cubic lattices bounded by various sizes of rectangle and rectangular cuboid respectively. The results of the computations are presented. Derived statistics are tabulated forming new sequences for the OEIS. Relationships to existing sequences are shown. Finally, the C++ program used to perform the computations is provided.
We define a path as a set of connected nodes in a lattice and its length as the number of connected nodes.
By the term “complete non-self-intersecting path”, we mean a non-extendable path such that no node within it can appear twice.
A distinctive property of a non-self-intersecting path is that, at some point in its construction, it cannot be extended any further and so can be regarded as complete. Such a path is illustrated below. It is also a longest CNSIP in a cubic lattice bounded by a rectangular cuboid with sides 4, 3 and 2 nodes long. Its length is 24 as it connects 24 nodes, the number of nodes in the lattice.
We have numbered the nodes in the constrained lattice above as follows:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
The example CNSIP can then be written as a sequence of node numbers:
- {0, 1, 2, 3, 7, 6, 5, 4, 8, 9, 10, 11, 23, 22, 21, 20, 16, 17, 18, 19, 15, 14, 13, 12}
We consider the shape of CNSIPs, of which length is one characteristic, and make the sole restriction that path shapes are invariant under rotation. A node-free means of specifying a CNSIP is necessary to compare and categorize CNSIPs. This is achieved by defining a sequence of directions of path progression. The number of directions is clearly one less than the number of nodes. If the directions in the horizontal plane are left (L), right (R), up (U) and down (D), and the directions in the vertical plane are above (A) and below (B), then the example CNSIP can be expressed as:
- {R, R, R, D, L, L, L, D, R, R, R, B, L, L, L, U, R, R, R, U, L, L, L}
Results
This section contains the raw results (with some manual additions) from a C++ program for calculating CNSIPs on a square or cubic lattice bounded by a rectangle or rectangular cuboid.
Square lattice
Sets of results are presented for the following values of a and b, where a and b are the length and width in nodes of the rectangle within which CNSAPs are constructed:
Full results
a b no. 2-25 2 24 3-17 3 15 4-12 4 9 5- 9 5 5 6- 7 6 2 7 7 1 Total 56
No CNSIP shape statistics
a b no. 18-25 3 8 13-20 4 8 10-16 5 7 8-13 6 6 8-11 7 4 8-10 8 3 9 9 1 Total 37
No CNSIP shape statistics are available for values of a and b for which the number of distinct CNSIP shapes exceeds the maximum number of elements that an array can have in C++. This limit is given by size_t, which is the maximum value of an unsigned integer (i.e. 2^32 - 1).
Where appropriate, results are presented so as to reflect the shape of the rectangle.
CNSIP shapes are indistinct under rotation only.
Each set of full results contains 5 sections:
- 1. For each significant path length L, the number of CNSIPs (C) and the number of different CNSIP shapes (S). For example, when a = b = 2, there is only one path length for which the number of CNSAPs is not zero, namely L = 4. There are 8 such CNSIPs in total and there are two distinct shapes, where one shape is the reflection of the other.
- 2. The number of times each node is the start node (SN) of a CNSIP of length L. For example, when a = b = 2, each of the four nodes 0, 1, 2 and 3 is the start node for 2 CNSIPs.
- 3. The number of times each node is the end node (EN) of a CNSIP of length L. For example, when a = b = 2, each of the four nodes 0, 1, 2 and 3 can be the end node for 2 CNSIPs.
- 4. The number of times each node (N) is present in a CNSIP of length L. For example, when a = b = 2, each of the four nodes 0, 1, 2 and 3 is present in 8 CNSIPs.
- 5. The number of CNSIPs for each start node (SN) and end node (EN) pair. For example, when a = b = 2, there is one CNSIP for which node 0 is the start node and node 1 is the end node. Also calculated for this table are:
- the number of distinct row element sets
- the number of rows as a linear combination of the distinct row element sets
- the number and the set of distinct values
- the number of SN-EN pairs for which the number of CNSAPs is greater than zero
- the number of SN-EN pairs, with SN and EN different, for which the number of CNSAPs equals zero
- the number of possible SN-EN pairs with SN and EN different.
Click on the link to see the results.
CNSIP:Results for square lattice
Cubic lattice
Sets of results are presented for the following values of a, b and c, where a, b and c are the length, width and height in nodes of the rectangular cuboid within which CNSIPs are constructed:
Full results
a b c no. 2-11 2 2 10 3- 7 3 2 5 3- 4 3 3 2 4- 5 4 2 2 Total 19
No CNSIP shape statistics
a b c no. 12-20 2 2 9 8-13 3 2 6 5- 9 3 3 5 6-10 4 2 5 4- 6 4 3 3 4- 5 4 4 2 5- 8 5 2 4 5 5 3 1 6 6 2 1 Total 36
No CNSIP shape statistics are available for values of a, b and c for which the number of distinct CNSIP shapes exceeds the maximum number of elements that an array can have in C++. This limit is given by size_t, which is the maximum value of an unsigned integer (i.e. 2^32 - 1).
Where appropriate, results are presented so as to reflect the shape of the rectangular cuboid.
CNSIP shapes are indistinct under rotation only.
Each set of full results contains 5 sections:
- 1. For each significant path length L, the number of CNSIPs (C) and the number of different CNSIP shapes (S). For example, when a = b = c = 2, there is only one path length for which the number of CNSIPs is not zero, namely L = ???. There are ??? such complete paths in total and there are two distinct shapes, where one shape is the reflection of the other.
- 2. The number of times each node is the start node (SN) of a CNSIP of length L. For example, when a = b = c = 2, each of the eight nodes 0, 1, 2, 3, 4, 5, 6 and 7 is the start node for ??? CNSAPs.
- 3. The number of times each node is the end node (EN) of a CNSAP of length L. For example, when a = b = c = 2, each of the eight nodes 0, 1, 2, 3, 4, 5, 6 and 7 is the end node for ??? CNSAPs.
- 4. The number of times each node (N) is present in a CNSAP of length L. For example, when a = b = c = 2, each of the eight nodes 0, 1, 2, 3, 4, 5, 6 and 7 is present in ??? CNSAPs.
- 5. The number of CNSAPs for each start node (SN) and end node (EN) pair. For example, when a = b = c = 2, there are ??? CNSAPs for which node 0 is the start node and node 3 is the end node. Also calculated for this table are:
- the number of distinct row element sets
- the number of rows as a linear combination of the distinct row element sets
- the number and the set of distinct values
- the number of SN-EN pairs for which the number of CNSIPs is greater than zero
- the number of SN-EN pairs, with SN and EN different, for which the number of CNSIPs equals zero
- the number of possible SN-EN pairs with SN and EN different.
Click on the link to see the results.
CNSIP:Results for cubic lattice
Analysis
This section contains an analysis of the results.
Program
The program used to calculate the results presented in this article can be viewed by clicking on the following link:
Computation
The run that took the longest to complete was for a = ???, b = ???, c = ???. It took just under ??? days of CPU time on an Intel Core i7 CPU 975 @ 3.33 GHz overclocked to 4 GHz.
