The recursive worker extends a current path by one uniformly selected unused neighbour. A trapped extension returns
NULL all the way to the outer loop, which restarts from the origin. It does not backtrack and try a different branch of the same attempt, since the stated process restarts the entire walk.saw <- function(N) {
stopifnot(length(N) == 1L, is.finite(N), N >= 0,
N == floor(N))
steps <- rbind(c(1L, 0L), c(-1L, 0L),
c(0L, 1L), c(0L, -1L))
grow <- function(path) {
if (nrow(path) == N + 1L) return(path)
last <- path[nrow(path), ]
candidates <- sweep(steps, 2L, last, "+")
keep <- vapply(seq_len(nrow(candidates)), function(i) {
!row.match(path, candidates[i, ])
}, logical(1))
candidates <- candidates[keep, , drop = FALSE]
if (nrow(candidates) == 0L) return(NULL)
j <- sample.int(nrow(candidates), 1L)
grow(rbind(path, candidates[j, ]))
}
repeat {
path <- grow(matrix(c(0L, 0L), nrow = 1L))
if (!is.null(path)) return(path)
}
}The base case has exactly visited vertices. Every extension is a unit horizontal or vertical step to a new vertex, proving the output dimensions and self-avoidance by induction. A straight path has positive probability, so each independent attempt has a positive chance of success and repeated attempts terminate almost surely.
The scheme is not uniform in general. A particular successful path has probability equal to the product of the reciprocals of its available-neighbour counts. Those counts depend on the path geometry.
For length four, the straight path has probability . The path has only two available neighbours at its last choice, because the previous point and the origin block two directions. Its probability is . There is no trapping before four steps, so these are already the output probabilities. They differ, disproving uniformity on .
At lengths where restarts occur, conditioning an attempt on success normalizes these path probabilities by a common success probability; it does not remove the unequal products.
A simple square-lattice polygon has even perimeter at least four. Generate a self-avoiding walk of length , reject unless its endpoint is a neighbour of the origin, then add the final edge to close it.
sap <- function(M) {
stopifnot(length(M) == 1L, is.finite(M), M >= 4,
M == floor(M), M %% 2 == 0)
repeat {
path <- saw(M - 1L)
if (sum(abs(path[nrow(path), ])) == 1L) {
return(rbind(path, c(0L, 0L)))
}
}
}The output has coordinate rows and unit edges. The first vertices are distinct by the call to
saw; the last row repeats only the origin. Neighbouring lattice edges cannot create an additional crossing without a repeated vertex. A rectangle of perimeter exists for every permitted even , giving a positive probability of eventual acceptance. Articles by others on the same topic
There are currently no matching articles.