1. Home
2. Questions
3. Tags
5. Users
6. Jobs
7. Companies
8. Unanswered
Teams

Ask questions, find answers and collaborate at work with Stack Overflow for Teams.
Try Teams for free Explore Teams
Teams
Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Return to Answer

added 466 characters in body

Source Link

edited Nov 23, 2018 at 10:33

2.6k
11
15

R, 112 107 10399 bytes

Non-recursive approach. We use "<" and ">" because it avoids escape characters in the regex. To allow us to use a shorter specification for an ASCII range, we generate all 2^2n3^2n 2n-character strings of "(""<", "=" and ")"">" using expand.grid (via their ASCII codes 4060, 61 and 4162) and then grep to see which combinations give balanced parenthesesopen and close brackets. The "=" possibilities will get ignored, of course.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\(<(?1)*\\)*>)(?1)*$",apply(expand.grid(rep(list(4160:4062),2*n)),1,intToUtf8),,T,T))

Try it online!Try it online!

Explanation

"^(\\(<(?1)*\\)*>)(?1)*$" = regex for balanced parens<> with no other characters
^ # match a start of the string
  ( # start of expression 1
    \\(< # open parens<>
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    \\)> # close parens<>
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(\\(<(?1)*\\)*>)(?1)*$", # search for regular expression matching parensopen and close brackets
      apply(
        expand.grid(rep(list(4160:4062),2*n)) # generate 2^3^(2n) 4060, 4161,62 combinations
      ,1,intToUtf8) # turn into all 2^3^(2n) combinations of "(""<",")""=",">"
    ,,T,T) # return the values that match the regex, so "=" gets ignored
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n 2n-character strings of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ # match a start of the string
  ( # start of expression 1
    \\( # open parens
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    \\) # close parens
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

R, 112 107 99 bytes

Non-recursive approach. We use "<" and ">" because it avoids escape characters in the regex. To allow us to use a shorter specification for an ASCII range, we generate 3^2n 2n-character strings of "<", "=" and ">" using expand.grid (via their ASCII codes 60, 61 and 62) and then grep to see which combinations give balanced open and close brackets. The "=" possibilities will get ignored, of course.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(<(?1)*>)(?1)*$",apply(expand.grid(rep(list(60:62),2*n)),1,intToUtf8),,T,T))

Explanation

"^(<(?1)*>)(?1)*$" = regex for balanced <> with no other characters
^ # match a start of the string
  ( # start of expression 1
    < # open <>
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    > # close <>
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(<(?1)*>)(?1)*$", # search for regular expression matching open and close brackets
      apply(
        expand.grid(rep(list(60:62),2*n)) # generate 3^(2n) 60,61,62 combinations
      ,1,intToUtf8) # turn into all 3^(2n) combinations of "<","=",">"
    ,,T,T) # return the values that match the regex, so "=" gets ignored
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

added 8 characters in body

Source Link

edited Nov 23, 2018 at 10:19

2.6k
11
15

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n 2n-character strings of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ # match a start of the string
$ match the( end# start of theexpression string1
(    \\(\\)) match# open andparens
 close parenthesises ()
(\\(    (?1)*\\))(?* # optional repeat of any number of expression 1 (recursive)*
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
^(    \\((?1)*\\) # close parens
  ) # end of expression 1
  (?1)*$* we# addoptional ^repeat andof $any tonumber consumeof theexpression whole1
$ # end of string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n 2n-character strings of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ match a start of the string
$ match the end of the string
(\\(\\)) match open and close parenthesises ()
(\\((?1)*\\))(?1)* match parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
^(\\((?1)*\\))(?1)*$ we add ^ and $ to consume the whole string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n 2n-character strings of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ # match a start of the string
  ( # start of expression 1
    \\( # open parens
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    \\) # close parens
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

added 8 characters in body

Source Link

edited Nov 23, 2018 at 10:14

2.6k
11
15

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n combinations2n-character strings of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ match a start of the string
$ match the end of the string
(\\(\\)) match open and close parenthesises ()
(\\((?1)*\\))(?1)* match parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
^(\\((?1)*\\))(?1)*$ we add ^ and $ to consume the whole string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n combinations of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ match a start of the string
$ match the end of the string
(\\(\\)) match open and close parenthesises ()
(\\((?1)*\\))(?1)* match parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
^(\\((?1)*\\))(?1)*$ we add ^ and $ to consume the whole string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

R, 112 107 103 bytes

Non-recursive approach. We generate all 2^2n 2n-character strings of "(" and ")" using expand.grid (via their ASCII codes 40 and 41) and then grep to see which combinations give balanced parentheses.

Via http://rachbelaid.com/recursive-regular-experession/

function(n)sort(grep("^(\\((?1)*\\))(?1)*$",apply(expand.grid(rep(list(41:40),2*n)),1,intToUtf8),,T,T))

Explanation

"^(\\((?1)*\\))(?1)*$" = regex for balanced parens
^ match a start of the string
$ match the end of the string
(\\(\\)) match open and close parenthesises ()
(\\((?1)*\\))(?1)* match parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
^(\\((?1)*\\))(?1)*$ we add ^ and $ to consume the whole string

function(n)
  sort(
    grep("^(\\((?1)*\\))(?1)*$", # search for regular expression matching parens
      apply(
        expand.grid(rep(list(41:40),2*n)) # generate 2^(2n) 40, 41 combinations
      ,1,intToUtf8) # turn into all 2^(2n) combinations of "(",")"
    ,,T,T) # return the values that match the regex
  ) # sort them

R, 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

Different non-recursive approach thanks to a regex.

Source Link

edited Nov 23, 2018 at 10:06

2.6k
11
15

Loading

added 43 characters in body

Source Link

edited Nov 21, 2018 at 10:09

2.6k
11
15

Loading

deleted 35 characters in body

Source Link

edited Nov 7, 2018 at 21:59

2.6k
11
15

Loading

deleted 19 characters in body

Source Link

edited Nov 6, 2018 at 22:33

2.6k
11
15

Loading

added 1 character in body

Source Link

edited Nov 6, 2018 at 22:23

2.6k
11
15

Loading

added 12 characters in body

Source Link

edited Nov 6, 2018 at 21:59

2.6k
11
15

Loading

deleted 14 characters in body

Source Link

edited Nov 6, 2018 at 21:44

2.6k
11
15

Loading

added 16 characters in body

Source Link

edited Nov 6, 2018 at 16:40

2.6k
11
15

Loading

added 13 characters in body

Source Link

edited Nov 6, 2018 at 16:19

2.6k
11
15

Loading

added 2 characters in body

Source Link

edited Nov 6, 2018 at 15:49

2.6k
11
15

Loading

Source Link

created Nov 6, 2018 at 15:36

2.6k
11
15

Loading