karstenw

brackets

Dec 5th, 2021
726
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Given a random string of n left brackets and n right brackets,
  2. # how often do you need to cut it into two parts and swap
  3. # both sides, to make it "algebraicaly valid"?
  4. rnd_x <- function(n) {
  5.     idx_rb <- sample.int(2*n, n)
  6.     x <- rep(1, 2*n)
  7.     x[idx_rb] <- -1
  8.     x
  9. }
  10.  
  11. as_br <- function(x) paste0(ifelse(x==1, "(", ")"))
  12.  
  13. one_x <- function(n) {
  14.     x <- rnd_x(n)
  15.     message(as_br(x))  
  16.     cx <- cumsum(x)
  17.     i <- 0
  18.     while (any(cx<0) && i<2*n) {
  19.         i <- i+1
  20.         br <- which.min(cx)
  21.         x <- c(x[seq(br+1,2*n)], x[1:br])
  22.         message(i,": ", as_br(x))
  23.         cx <- cumsum(x)
  24.     }
  25.     i
  26. }
  27.  
  28. lapply(1:10, function(n) max(replicate(10^3, one_x(n))))
  29.  
RAW Paste Data