brackets

# Given a random string of n left brackets and n right brackets,
# how often do you need to cut it into two parts and swap
# both sides, to make it "algebraicaly valid"?
rnd_x <- function(n) {
    idx_rb <- sample.int(2*n, n)
    x <- rep(1, 2*n)
    x[idx_rb] <- -1
    x
}

as_br <- function(x) paste0(ifelse(x==1, "(", ")"))

one_x <- function(n) {
    x <- rnd_x(n)
    message(as_br(x))
    cx <- cumsum(x)
    i <- 0
    while (any(cx<0) && i<2*n) {
        i <- i+1
        br <- which.min(cx)
        x <- c(x[seq(br+1,2*n)], x[1:br])
        message(i,": ", as_br(x))
        cx <- cumsum(x)
    }
    i
}

lapply(1:10, function(n) max(replicate(10^3, one_x(n))))