This site is supported by donations to The OEIS Foundation.
Complete non-self-adjacent paths
This is the Contents
Complete non-self-adjacent paths in bounded square and cubic lattices
Chris Gribble is currently working on this topic.
Acknowledgements
Tom Young, a math teacher at Spring Lake Park Senior High School, Minnesota, made several major contributions in the early part of the project. He had the original idea that sparked off this project, to compute the longest non-self-adjacent path in a cubic lattice bounded by a cube. He also developed Liberty Basic and C++ precursors to the program used to calculate the results for this article.
Introduction
Since July 2010, with key initial input from Tom Young, I have computed all complete non-self-adjacent paths (CNSAPs) 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. A method for minimizing the computation required is derived. Methods for estimating the longest CNSAP in bounded square and cubic lattices are given. Finally, the C++ program used to perform the computations is provided.
A path in a lattice is a sequence of connected nodes. We assume that a path is:
- Simple, with no node in the sequence occurring more than once;
- Directional, with a start node and and an end node;
- Finite, with different start and end nodes.
We define the length of a path to be the number of connected nodes.
By the term “complete non-self-adjacent path”, we mean a non-extendable path such that no two nodes within it that are not directly connected can be adjacent to one another. The latter restriction can be also expressed as follows:
- Only one of the neighboring nodes to the start node can be present in the path.
- Only one of the neighboring nodes to the end node can be present in the path.
- Only two of the neighboring nodes to each intermediate node can be present in the path.
A distinctive property of a non-self-adjacent 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 CNSAP in a cubic lattice bounded by a cube with side 3 nodes long. Its length is 16 as it connects 16 nodes.
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
24 25 26
The example CNSAP can then be written as a sequence of node numbers:
- {0, 1, 2, 5, 8, 7, 6, 15, 12, 21, 18, 19, 20, 23, 26, 25}
We consider the shape of CNSAPs, 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 CNSAP is necessary to compare and categorize CNSAPs. 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 left, right, above (A) and below (B), then the example CNSAP can be expressed as:
- {R, R, D, D, L, L, B, U, B, U, R, R, D, D, L}
Results
This section contains the raw results (with some manual additions) from a C++ program for calculating CNSAPs 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 width and height in nodes of the rectangle within which CNSAPs are constructed. For example, in the constrained lattice below, a = 3 and b = 2.
0 1 2
3 4 5
Full results
a b no. 2-25 2 24 3-18 3 16 4-12 4 9 5- 9 5 5 6- 7 6 2 7 7 1 Total 57
No CNSAP shape statistics
a b no. 19-25 3 7 13-20 4 8 10-16 5 7 8-13 6 6 8-11 7 4 8-10 8 3 9 9 1 Total 36
No CNSAP shape statistics are available for values of a and b for which the number of distinct CNSAP 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.
CNSAP shapes are indistinct under rotation only.
Each set of full results contains 5 sections:
- 1. For each significant path length L, the number of CNSAPs (C) and the number of different CNSAP 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 = 3. There are 8 such CNSAPs 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 CNSAP 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 CNSAPs.
- 3. The number of times each node is the end node (EN) of a CNSAP 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 CNSAPs.
- 4. The number of times each node (N) is present in a CNSAP of length L. For example, when a = b = 2, each of the four nodes 0, 1, 2 and 3 is present in 6 CNSAPs.
- 5. The number of CNSAPs for each start node (SN) and end node (EN) pair. For example, when a = b = 2, there are two CNSAPs for which node 0 is the start node and node 3 is the end node. Also calculated for this table are:
- the sum of all rows as a linear combination of the distinct row value sets
- the sum of all value frequencies as a linear combination of the distinct row value frequencies
- the number of distinct row element sets
- the number of rows as a linear combination of the distinct row element set multiples
- the number of distinct values
- the set of distinct values and their frequencies of occurrence
- the sum of the frequencies taken over all 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.
Complete non-self-adjacent paths: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 width, depth and height in nodes of the rectangular cuboid within which CNSAPs are constructed. For example, in the constrained lattice below, a = 4, b = 3 and c = 2.
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
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 CNSAP 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 CNSAP shape statistics are available for values of a, b and c for which the number of distinct CNSAP 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.
CNSAP shapes are indistinct under rotation only.
Each set of full results contains 5 sections:
- 1. For each significant path length L, the number of CNSAPs (C) and the number of different CNSAP shapes (S). For example, when a = b = c = 2, there is only one path length for which the number of CNSAPs is not zero, namely L = 5. There are 48 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 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 start node for 6 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 6 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 30 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 two CNSAPs for which node 0 is the start node and node 3 is the end node. Also calculated for this table are:
- the sum of all rows as a linear combination of the distinct row value sets
- the sum of all value frequencies as a linear combination of the distinct row value frequencies
- the number of distinct row element sets
- the number of rows as a linear combination of the distinct row element set multiples
- the number of distinct values
- the set of distinct values and their frequencies of occurrence
- the sum of the frequencies taken over all 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.
Complete non-self-adjacent paths:Results_for_Cubic_Lattice
Sequences
The following sequences have been added to the OEIS:
Irregular array T(n,k) of numbers/2 of non-extendable (complete) non-self-adjacent simple paths of each length within a square lattice bounded by rectangles with nodal dimensions n and c, n >= 2:
A213274 c = 2, A213089 c = 3, A213342 c = 4, A213375 c = 5, A213379 c = 6, A213383 c = 7, A213425 c = 8, A213426 c = 9
Irregular array T(n,k) of the numbers of distinct shapes under rotation of the non-extendable (complete) non-self-adjacent simple paths of each length within a square lattice bounded by rectangles with nodal dimensions n and c, n >= 2:
A213431 c = 2, A213433 c = 3, A213473 c = 4, A213474 c = 5, A213475 c = 6, A213476 c = 7
Irregular array T(n,k) of the numbers of non-extendable (complete) non-self-adjacent simple paths starting at each of a minimal subset of nodes within a square lattice bounded by rectangles with nodal dimensions n and c, n >= 2:
A213478 c = 2, A213954 c = 3, A214022 c = 4, A214023 c = 5, A214025 c = 6, A214037 c = 7, A214038 c = 8, A214042 c = 9
Irregular array T(n,k) of the numbers of non-extendable (complete) non-self-adjacent simple paths ending at each of a minimal subset of nodes within a square lattice bounded by rectangles with nodal dimensions n and c, n >= 2:
A214119 c = 2, A214121 c = 3, A214122 c = 4, A214359 c = 5, A213070 c = 6, A214373 c = 7, A214375 c = 8, A214376 c = 9
Irregular array T(n,k) of the numbers of non-extendable (complete) non-self-adjacent simple paths incorporating each of a minimal subset of nodes within a square lattice bounded by rectangles with nodal dimensions n and c, n >= 2:
A214399 c = 2, A214504 c = 3, A214510 c = 4, A214563 c = 5, A214601 c = 6, A214503 c = 7, A214605 c = 8, A214608 c = 9
A213106 Triangle T(n,k) of numbers/2 of non-extendable (complete) non-self-adjacent simple paths within a square lattice bounded by rectangles with nodal dimensions n and k, n >= k >= 2.
A213249 Triangle T(n,k) of numbers of distinct shapes under rotation of non-extendable (complete) non-self-adjacent simple paths within a square lattice bounded by rectangles with nodal dimensions n and k, n >= k >= 2.
A214397 Triangle T(n,k) of the numbers of nodes in all non-extendable (complete) non-self-adjacent simple paths within a square lattice bounded by rectangles with nodal dimensions n and k, n >= k >= 2.
A215107 Triangle read by rows: T(n,k) is the nodal length of the longest non-extendable (complete) non-self-adjacent simple path within a square lattice bounded by rectangles with nodal dimensions n and k, n >= k >= 2.
Analysis
This section contains an analysis of the results.
Complete non-self-adjacent paths:Analysis
Program
The program used to calculate the results presented in this article can be viewed by clicking on the following link:
Complete non-self-adjacent paths:Program
Computation
The run that took the longest to complete was for a = 5, b = 4, c = 4. It took just under 50 days of CPU time on an Intel Core i7 CPU 975 @ 3.33 GHz overclocked to 4 GHz.
