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.
Articles by others on the same topic
There are currently no matching articles.