# Non-Simple Lattice Paths using PathGraph

I am encoding a lattice walk of steps North, South and East on $\mathbb{Z}^{2}$ between the two extremities of the $x$-axis:

T1 = Permutations[{N, N, S, S, E, E}, {6}][[4]];
T2 = {1};
For[i = 1, i <= 6, i++,
If[T1[[i]] == N,
T2 = Append[T2, T2[[i]] + 1]];
If[T1[[i]] == E, T2 = Append[T2, T2[[i]] + 3]];
If[T1[[i]] == S, T2 = Append[T2, T2[[i]] - 1]];]
T2
With[{n = 3}, g = GridGraph[{n, n}];
HighlightGraph[g, PathGraph@#] & /@ {T2}]
T2 = {1};


This code plots the 4th permutation in the list, which is T1={N,N,E,S,S,E}, and finally resets. This looks like:

However, I cannot plot certain permutations because they are not simple paths. For example {N,N,S,S,E,E} goes over itself: twice N, twice S (then carries on twice E). So it can't be displayed. Try using T1 = {N,N,S,S,E,E}.

Can this be fixed?

(Also, if possible, it would be nice to delete all permutations that go under the $x$-axis at some point, such as {S,S,N,N,E,E}.)

## 1 Answer

T1


{N, N, S, S, E, E}

T2


{1, 2, 3, 2, 1, 4, 7}

With[{n = 3}, g = GridGraph[{n, n}];
HighlightGraph[ g,
{UndirectedEdge @@@ Partition[#, 2, 1],
Style[#, Red]}] & /@ {T2}]


aside, I'd recommend using strings "N","S","E" instead of symbols. Especially N and E since they are reserved system symbols.

• Thank you, this will work great. – LordCrulos1337 Oct 21 '16 at 19:38