Parentheses sequences in lexicographical order
up vote
5
down vote
favorite
Challenge Taken from here and also here
An n parentheses sequence consists of n (
s and n )
s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example,
(())
is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes()
, then you can make it empty.
)()(
is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes)(
and you cannot erase any more
Task
Given a number n you need to generate all correct parenthesis sequence in lexicographical order
Output can be an array, list or string (in this case a sequence per line)
You can use a different pair of parenthesis such as {}
, ,
()
or any open-close sign
Example
n = 3
((()))
(()())
(())()
()(())
()()()
n = 2
(())
()()
code-golf balanced-string
|
show 3 more comments
up vote
5
down vote
favorite
Challenge Taken from here and also here
An n parentheses sequence consists of n (
s and n )
s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example,
(())
is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes()
, then you can make it empty.
)()(
is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes)(
and you cannot erase any more
Task
Given a number n you need to generate all correct parenthesis sequence in lexicographical order
Output can be an array, list or string (in this case a sequence per line)
You can use a different pair of parenthesis such as {}
, ,
()
or any open-close sign
Example
n = 3
((()))
(()())
(())()
()(())
()()()
n = 2
(())
()()
code-golf balanced-string
@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
Nov 6 at 14:12
Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6 at 14:13
1
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
Nov 6 at 14:23
3
Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets)
– user202729
Nov 6 at 14:24
Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like1
s and-1
s)?
– Jonathan Allan
Nov 6 at 19:51
|
show 3 more comments
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Challenge Taken from here and also here
An n parentheses sequence consists of n (
s and n )
s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example,
(())
is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes()
, then you can make it empty.
)()(
is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes)(
and you cannot erase any more
Task
Given a number n you need to generate all correct parenthesis sequence in lexicographical order
Output can be an array, list or string (in this case a sequence per line)
You can use a different pair of parenthesis such as {}
, ,
()
or any open-close sign
Example
n = 3
((()))
(()())
(())()
()(())
()()()
n = 2
(())
()()
code-golf balanced-string
Challenge Taken from here and also here
An n parentheses sequence consists of n (
s and n )
s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example,
(())
is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes()
, then you can make it empty.
)()(
is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes)(
and you cannot erase any more
Task
Given a number n you need to generate all correct parenthesis sequence in lexicographical order
Output can be an array, list or string (in this case a sequence per line)
You can use a different pair of parenthesis such as {}
, ,
()
or any open-close sign
Example
n = 3
((()))
(()())
(())()
()(())
()()()
n = 2
(())
()()
code-golf balanced-string
code-golf balanced-string
edited Nov 7 at 20:02
Laikoni
19.4k43596
19.4k43596
asked Nov 6 at 14:04
Luis felipe De jesus Munoz
3,91911253
3,91911253
@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
Nov 6 at 14:12
Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6 at 14:13
1
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
Nov 6 at 14:23
3
Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets)
– user202729
Nov 6 at 14:24
Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like1
s and-1
s)?
– Jonathan Allan
Nov 6 at 19:51
|
show 3 more comments
@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
Nov 6 at 14:12
Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6 at 14:13
1
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
Nov 6 at 14:23
3
Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets)
– user202729
Nov 6 at 14:24
Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like1
s and-1
s)?
– Jonathan Allan
Nov 6 at 19:51
@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
Nov 6 at 14:12
@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
Nov 6 at 14:12
Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6 at 14:13
Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6 at 14:13
1
1
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
Nov 6 at 14:23
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
Nov 6 at 14:23
3
3
Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets)
– user202729
Nov 6 at 14:24
Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets)
– user202729
Nov 6 at 14:24
Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like
1
s and -1
s)?– Jonathan Allan
Nov 6 at 19:51
Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like
1
s and -1
s)?– Jonathan Allan
Nov 6 at 19:51
|
show 3 more comments
13 Answers
13
active
oldest
votes
up vote
7
down vote
Perl 6, 36 bytes
{grep {try !.EVAL},[X~] <[ ]>xx$_*2}
Try it online!
Finds all lexographically sorted combinations of $2n$ s and filters the ones that
EVAL
correctly. Note that all valid combinations (even stuff like ) evaluate to
(which is falsey, but we
not
it (!
) to distinguish from try
returning Nil
)
Explanation:
{ } # Anonymous code block
<[ ]> # Create a list of ("[", "]")
xx$_*2 # Duplicate this 2n times
[X~] # Find all possible combinations
grep { }, # Filter from these
.EVAL # The EVAL'd strings
try ! # That do not throw an error
1
If anyone's curious,is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so
...
evaluates to. Besides,
[]
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write[,]
for a nested array). So any balanced sequence ofbrackets results in an empty array which boolifies to false.
– nwellnhof
Nov 7 at 10:48
add a comment |
up vote
4
down vote
Python 2, 91 88 84 81 bytes
f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']
Try it online!
-3 bytes thanks to pizzapants184
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
You can replaceset(...)
with a set comprehension ({...}
) for -3 bytes Try it online!
– pizzapants184
Nov 7 at 15:45
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
add a comment |
up vote
3
down vote
05AB1E, 13 bytes
„()©s·ãʒ®õ:õQ
Try it online or verify some more test cases.
Explanation:
„() # Push string "()"
© # Store it in the register without popping
s· # Swap to get the (implicit) input, and double it
ã # Cartesian product that many times
ʒ # Filter it by:
® # Push the "()" from the register
õ: # Infinite replacement with an empty string
õQ # And only keep those which are empty after the infinite replacement
add a comment |
up vote
3
down vote
Japt, 15 bytes
ç"" á Ôke/
Try it
Explanation
ç"" :Input times repeat the string ""
á :Get unique permutations
Ô :Reverse
k :Remove any that return true (non-empty string)
e/ : Recursively replace /[]/g
add a comment |
up vote
2
down vote
JavaScript (ES6), 112 102 bytes
This is heavily based on nwellnhof's C answer.
f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)
Try it online!
add a comment |
up vote
2
down vote
R, 112 108 bytes
Usual recursive approach.
-1 thanks @Giuseppe
-4 with a change to the Map
call.
b=40:41
f=function(n,x=b)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=b))))),intToUtf8(x))
Try it online!
1
ah, I was trying to find aMap
golf but couldn't wrap my head around it. I'm not convincedparse
+eval
is going to work since()()
and the like throw errors.
– Giuseppe
Nov 7 at 20:03
add a comment |
up vote
1
down vote
Ruby, 70 bytes
f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|}
Try it online!
add a comment |
up vote
1
down vote
C (gcc), 114 bytes
f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}
Try it online!
Should work for n <= 15.
Explanation
f(n,x,s,a,i){
char b[99]={}; // Output buffer initialized with zeros.
n*=2; // Double n.
for(x=1<<n;x--; // Loop from x=2**n-1 to 0, x is a bit field
// where 1 represents '(' and 0 represents ')'.
// This guarantees lexicographical order.
s|a<0||puts(b)) // Print buffer if s==0 (as many opening as
// closing parens) and a>=0 (number of open
// parens never drops below zero).
for(s=a=i=0;i<n;) // Loop from i=0 to n-1, note that we're
// traversing the bit field right-to-left.
a|= // a is the or-sum of all intermediate sums,
// it becomes negative whenever an intermediate
// sum is negative.
s+= // s is the number of closing parens minus the
// number of opening parens.
x>>i++&1 // Isolate current bit and inc i.
41-( ) // ASCII code of paren, a one bit
// yields 40 '(', a zero bit 41 ')'.
b[n-i]= // Store ASCII code in buffer.
2*( )-81; // 1 for ')' and -1 for '(' since
// we're going right-to-left.
}
add a comment |
up vote
1
down vote
Perl 6, 42 bytes
{grep {!S:g/(<~~>*)//},[X~] <( )>xx$_*2}
Try it online!
Uses a recursive regex. Alternative substitution: S/[(<~~>)]*//
38 bytes with 0 and 1 as open/close symbols:
{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}
Try it online!
Explanation
{ } # Anonymous block
<( )> # List "(", ")"
xx$_*2 # repeated 2n times
[X~] # Cartesian product with string concat
# yields all strings of length 2n
# consisting of ( and )
grep { }, # Filter strings
S:g/ # Globally replace regex match
( # literal (
<~~> # whole regex matched recursively
* # zero or more times
) # literal )
// # with empty string
! # Is empty string?
add a comment |
up vote
0
down vote
Perl 5 -n
, 41 39 bytes
-2 bytes with angle brackets
s/<(?R)*>//gr||say for glob'{<,>}'x2x$_
Try it online!
Port of my Perl 6 answer.
add a comment |
up vote
0
down vote
Jelly, 19 bytes
Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(
Try it online!
Output clarified over TIO.
add a comment |
up vote
0
down vote
Red, 214 184 bytes
func[n][p:""c: 2 ** d: 2 * n b: copyuntil[a: copy""e: c - 1 loop d[append a p/(e % 2 + 1)
e: e / 2]if not error? try[load a][append/only b a]1 > c: c - 1]foreach a sort b[print a]]
Try it online!
Uses Jo King's approach. Finds all possilble aarangements of brackes by base-2 convertion and then checks if the arrangement evaluates as a valid block.
add a comment |
up vote
0
down vote
Retina 0.8.2, 50 bytes
.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)
Try it online! Uses <>
s. Explanation:
.+
$*
Convert to unary.
1
11
Double the result.
+%1`1
<$'¶$`>
Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to <>
.
Gm`^(?<-1>(<)*>)*$(?(1).)
Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.
add a comment |
13 Answers
13
active
oldest
votes
13 Answers
13
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
Perl 6, 36 bytes
{grep {try !.EVAL},[X~] <[ ]>xx$_*2}
Try it online!
Finds all lexographically sorted combinations of $2n$ s and filters the ones that
EVAL
correctly. Note that all valid combinations (even stuff like ) evaluate to
(which is falsey, but we
not
it (!
) to distinguish from try
returning Nil
)
Explanation:
{ } # Anonymous code block
<[ ]> # Create a list of ("[", "]")
xx$_*2 # Duplicate this 2n times
[X~] # Find all possible combinations
grep { }, # Filter from these
.EVAL # The EVAL'd strings
try ! # That do not throw an error
1
If anyone's curious,is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so
...
evaluates to. Besides,
[]
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write[,]
for a nested array). So any balanced sequence ofbrackets results in an empty array which boolifies to false.
– nwellnhof
Nov 7 at 10:48
add a comment |
up vote
7
down vote
Perl 6, 36 bytes
{grep {try !.EVAL},[X~] <[ ]>xx$_*2}
Try it online!
Finds all lexographically sorted combinations of $2n$ s and filters the ones that
EVAL
correctly. Note that all valid combinations (even stuff like ) evaluate to
(which is falsey, but we
not
it (!
) to distinguish from try
returning Nil
)
Explanation:
{ } # Anonymous code block
<[ ]> # Create a list of ("[", "]")
xx$_*2 # Duplicate this 2n times
[X~] # Find all possible combinations
grep { }, # Filter from these
.EVAL # The EVAL'd strings
try ! # That do not throw an error
1
If anyone's curious,is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so
...
evaluates to. Besides,
[]
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write[,]
for a nested array). So any balanced sequence ofbrackets results in an empty array which boolifies to false.
– nwellnhof
Nov 7 at 10:48
add a comment |
up vote
7
down vote
up vote
7
down vote
Perl 6, 36 bytes
{grep {try !.EVAL},[X~] <[ ]>xx$_*2}
Try it online!
Finds all lexographically sorted combinations of $2n$ s and filters the ones that
EVAL
correctly. Note that all valid combinations (even stuff like ) evaluate to
(which is falsey, but we
not
it (!
) to distinguish from try
returning Nil
)
Explanation:
{ } # Anonymous code block
<[ ]> # Create a list of ("[", "]")
xx$_*2 # Duplicate this 2n times
[X~] # Find all possible combinations
grep { }, # Filter from these
.EVAL # The EVAL'd strings
try ! # That do not throw an error
Perl 6, 36 bytes
{grep {try !.EVAL},[X~] <[ ]>xx$_*2}
Try it online!
Finds all lexographically sorted combinations of $2n$ s and filters the ones that
EVAL
correctly. Note that all valid combinations (even stuff like ) evaluate to
(which is falsey, but we
not
it (!
) to distinguish from try
returning Nil
)
Explanation:
{ } # Anonymous code block
<[ ]> # Create a list of ("[", "]")
xx$_*2 # Duplicate this 2n times
[X~] # Find all possible combinations
grep { }, # Filter from these
.EVAL # The EVAL'd strings
try ! # That do not throw an error
edited Nov 6 at 22:53
answered Nov 6 at 14:20
Jo King
19k242101
19k242101
1
If anyone's curious,is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so
...
evaluates to. Besides,
[]
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write[,]
for a nested array). So any balanced sequence ofbrackets results in an empty array which boolifies to false.
– nwellnhof
Nov 7 at 10:48
add a comment |
1
If anyone's curious,is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so
...
evaluates to. Besides,
[]
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write[,]
for a nested array). So any balanced sequence ofbrackets results in an empty array which boolifies to false.
– nwellnhof
Nov 7 at 10:48
1
1
If anyone's curious,
is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so ...
evaluates to
. Besides, []
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write [,]
for a nested array). So any balanced sequence of
brackets results in an empty array which boolifies to false.– nwellnhof
Nov 7 at 10:48
If anyone's curious,
is the Zen slice of an empty array which yields the array itself. The slice can be applied multiple times, so ...
evaluates to
. Besides, []
doesn't construct a nested array but an empty array because of the single argument rule (you'd have to write [,]
for a nested array). So any balanced sequence of
brackets results in an empty array which boolifies to false.– nwellnhof
Nov 7 at 10:48
add a comment |
up vote
4
down vote
Python 2, 91 88 84 81 bytes
f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']
Try it online!
-3 bytes thanks to pizzapants184
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
You can replaceset(...)
with a set comprehension ({...}
) for -3 bytes Try it online!
– pizzapants184
Nov 7 at 15:45
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
add a comment |
up vote
4
down vote
Python 2, 91 88 84 81 bytes
f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']
Try it online!
-3 bytes thanks to pizzapants184
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
You can replaceset(...)
with a set comprehension ({...}
) for -3 bytes Try it online!
– pizzapants184
Nov 7 at 15:45
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
add a comment |
up vote
4
down vote
up vote
4
down vote
Python 2, 91 88 84 81 bytes
f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']
Try it online!
-3 bytes thanks to pizzapants184
Python 2, 91 88 84 81 bytes
f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']
Try it online!
-3 bytes thanks to pizzapants184
edited Nov 8 at 7:46
answered Nov 6 at 14:27
TFeld
13.4k21039
13.4k21039
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
You can replaceset(...)
with a set comprehension ({...}
) for -3 bytes Try it online!
– pizzapants184
Nov 7 at 15:45
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
add a comment |
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
You can replaceset(...)
with a set comprehension ({...}
) for -3 bytes Try it online!
– pizzapants184
Nov 7 at 15:45
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
Also works in Python 3, I think
– SuperStormer
Nov 7 at 0:02
You can replace
set(...)
with a set comprehension ({...}
) for -3 bytes Try it online!– pizzapants184
Nov 7 at 15:45
You can replace
set(...)
with a set comprehension ({...}
) for -3 bytes Try it online!– pizzapants184
Nov 7 at 15:45
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
@pizzapants184 Thanks :)
– TFeld
Nov 8 at 7:46
add a comment |
up vote
3
down vote
05AB1E, 13 bytes
„()©s·ãʒ®õ:õQ
Try it online or verify some more test cases.
Explanation:
„() # Push string "()"
© # Store it in the register without popping
s· # Swap to get the (implicit) input, and double it
ã # Cartesian product that many times
ʒ # Filter it by:
® # Push the "()" from the register
õ: # Infinite replacement with an empty string
õQ # And only keep those which are empty after the infinite replacement
add a comment |
up vote
3
down vote
05AB1E, 13 bytes
„()©s·ãʒ®õ:õQ
Try it online or verify some more test cases.
Explanation:
„() # Push string "()"
© # Store it in the register without popping
s· # Swap to get the (implicit) input, and double it
ã # Cartesian product that many times
ʒ # Filter it by:
® # Push the "()" from the register
õ: # Infinite replacement with an empty string
õQ # And only keep those which are empty after the infinite replacement
add a comment |
up vote
3
down vote
up vote
3
down vote
05AB1E, 13 bytes
„()©s·ãʒ®õ:õQ
Try it online or verify some more test cases.
Explanation:
„() # Push string "()"
© # Store it in the register without popping
s· # Swap to get the (implicit) input, and double it
ã # Cartesian product that many times
ʒ # Filter it by:
® # Push the "()" from the register
õ: # Infinite replacement with an empty string
õQ # And only keep those which are empty after the infinite replacement
05AB1E, 13 bytes
„()©s·ãʒ®õ:õQ
Try it online or verify some more test cases.
Explanation:
„() # Push string "()"
© # Store it in the register without popping
s· # Swap to get the (implicit) input, and double it
ã # Cartesian product that many times
ʒ # Filter it by:
® # Push the "()" from the register
õ: # Infinite replacement with an empty string
õQ # And only keep those which are empty after the infinite replacement
answered Nov 6 at 14:29
Kevin Cruijssen
33.7k554179
33.7k554179
add a comment |
add a comment |
up vote
3
down vote
Japt, 15 bytes
ç"" á Ôke/
Try it
Explanation
ç"" :Input times repeat the string ""
á :Get unique permutations
Ô :Reverse
k :Remove any that return true (non-empty string)
e/ : Recursively replace /[]/g
add a comment |
up vote
3
down vote
Japt, 15 bytes
ç"" á Ôke/
Try it
Explanation
ç"" :Input times repeat the string ""
á :Get unique permutations
Ô :Reverse
k :Remove any that return true (non-empty string)
e/ : Recursively replace /[]/g
add a comment |
up vote
3
down vote
up vote
3
down vote
Japt, 15 bytes
ç"" á Ôke/
Try it
Explanation
ç"" :Input times repeat the string ""
á :Get unique permutations
Ô :Reverse
k :Remove any that return true (non-empty string)
e/ : Recursively replace /[]/g
Japt, 15 bytes
ç"" á Ôke/
Try it
Explanation
ç"" :Input times repeat the string ""
á :Get unique permutations
Ô :Reverse
k :Remove any that return true (non-empty string)
e/ : Recursively replace /[]/g
edited Nov 6 at 15:39
answered Nov 6 at 14:41
Shaggy
17.9k21663
17.9k21663
add a comment |
add a comment |
up vote
2
down vote
JavaScript (ES6), 112 102 bytes
This is heavily based on nwellnhof's C answer.
f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)
Try it online!
add a comment |
up vote
2
down vote
JavaScript (ES6), 112 102 bytes
This is heavily based on nwellnhof's C answer.
f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)
Try it online!
add a comment |
up vote
2
down vote
up vote
2
down vote
JavaScript (ES6), 112 102 bytes
This is heavily based on nwellnhof's C answer.
f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)
Try it online!
JavaScript (ES6), 112 102 bytes
This is heavily based on nwellnhof's C answer.
f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)
Try it online!
edited Nov 7 at 8:12
answered Nov 6 at 14:32
Arnauld
68.5k584289
68.5k584289
add a comment |
add a comment |
up vote
2
down vote
R, 112 108 bytes
Usual recursive approach.
-1 thanks @Giuseppe
-4 with a change to the Map
call.
b=40:41
f=function(n,x=b)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=b))))),intToUtf8(x))
Try it online!
1
ah, I was trying to find aMap
golf but couldn't wrap my head around it. I'm not convincedparse
+eval
is going to work since()()
and the like throw errors.
– Giuseppe
Nov 7 at 20:03
add a comment |
up vote
2
down vote
R, 112 108 bytes
Usual recursive approach.
-1 thanks @Giuseppe
-4 with a change to the Map
call.
b=40:41
f=function(n,x=b)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=b))))),intToUtf8(x))
Try it online!
1
ah, I was trying to find aMap
golf but couldn't wrap my head around it. I'm not convincedparse
+eval
is going to work since()()
and the like throw errors.
– Giuseppe
Nov 7 at 20:03
add a comment |
up vote
2
down vote
up vote
2
down vote
R, 112 108 bytes
Usual recursive approach.
-1 thanks @Giuseppe
-4 with a change to the Map
call.
b=40:41
f=function(n,x=b)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=b))))),intToUtf8(x))
Try it online!
R, 112 108 bytes
Usual recursive approach.
-1 thanks @Giuseppe
-4 with a change to the Map
call.
b=40:41
f=function(n,x=b)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=b))))),intToUtf8(x))
Try it online!
edited Nov 7 at 21:59
answered Nov 6 at 15:36
J.Doe
1,931112
1,931112
1
ah, I was trying to find aMap
golf but couldn't wrap my head around it. I'm not convincedparse
+eval
is going to work since()()
and the like throw errors.
– Giuseppe
Nov 7 at 20:03
add a comment |
1
ah, I was trying to find aMap
golf but couldn't wrap my head around it. I'm not convincedparse
+eval
is going to work since()()
and the like throw errors.
– Giuseppe
Nov 7 at 20:03
1
1
ah, I was trying to find a
Map
golf but couldn't wrap my head around it. I'm not convinced parse
+ eval
is going to work since ()()
and the like throw errors.– Giuseppe
Nov 7 at 20:03
ah, I was trying to find a
Map
golf but couldn't wrap my head around it. I'm not convinced parse
+ eval
is going to work since ()()
and the like throw errors.– Giuseppe
Nov 7 at 20:03
add a comment |
up vote
1
down vote
Ruby, 70 bytes
f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|}
Try it online!
add a comment |
up vote
1
down vote
Ruby, 70 bytes
f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|}
Try it online!
add a comment |
up vote
1
down vote
up vote
1
down vote
Ruby, 70 bytes
f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|}
Try it online!
Ruby, 70 bytes
f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|}
Try it online!
answered Nov 6 at 15:19
G B
7,4661327
7,4661327
add a comment |
add a comment |
up vote
1
down vote
C (gcc), 114 bytes
f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}
Try it online!
Should work for n <= 15.
Explanation
f(n,x,s,a,i){
char b[99]={}; // Output buffer initialized with zeros.
n*=2; // Double n.
for(x=1<<n;x--; // Loop from x=2**n-1 to 0, x is a bit field
// where 1 represents '(' and 0 represents ')'.
// This guarantees lexicographical order.
s|a<0||puts(b)) // Print buffer if s==0 (as many opening as
// closing parens) and a>=0 (number of open
// parens never drops below zero).
for(s=a=i=0;i<n;) // Loop from i=0 to n-1, note that we're
// traversing the bit field right-to-left.
a|= // a is the or-sum of all intermediate sums,
// it becomes negative whenever an intermediate
// sum is negative.
s+= // s is the number of closing parens minus the
// number of opening parens.
x>>i++&1 // Isolate current bit and inc i.
41-( ) // ASCII code of paren, a one bit
// yields 40 '(', a zero bit 41 ')'.
b[n-i]= // Store ASCII code in buffer.
2*( )-81; // 1 for ')' and -1 for '(' since
// we're going right-to-left.
}
add a comment |
up vote
1
down vote
C (gcc), 114 bytes
f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}
Try it online!
Should work for n <= 15.
Explanation
f(n,x,s,a,i){
char b[99]={}; // Output buffer initialized with zeros.
n*=2; // Double n.
for(x=1<<n;x--; // Loop from x=2**n-1 to 0, x is a bit field
// where 1 represents '(' and 0 represents ')'.
// This guarantees lexicographical order.
s|a<0||puts(b)) // Print buffer if s==0 (as many opening as
// closing parens) and a>=0 (number of open
// parens never drops below zero).
for(s=a=i=0;i<n;) // Loop from i=0 to n-1, note that we're
// traversing the bit field right-to-left.
a|= // a is the or-sum of all intermediate sums,
// it becomes negative whenever an intermediate
// sum is negative.
s+= // s is the number of closing parens minus the
// number of opening parens.
x>>i++&1 // Isolate current bit and inc i.
41-( ) // ASCII code of paren, a one bit
// yields 40 '(', a zero bit 41 ')'.
b[n-i]= // Store ASCII code in buffer.
2*( )-81; // 1 for ')' and -1 for '(' since
// we're going right-to-left.
}
add a comment |
up vote
1
down vote
up vote
1
down vote
C (gcc), 114 bytes
f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}
Try it online!
Should work for n <= 15.
Explanation
f(n,x,s,a,i){
char b[99]={}; // Output buffer initialized with zeros.
n*=2; // Double n.
for(x=1<<n;x--; // Loop from x=2**n-1 to 0, x is a bit field
// where 1 represents '(' and 0 represents ')'.
// This guarantees lexicographical order.
s|a<0||puts(b)) // Print buffer if s==0 (as many opening as
// closing parens) and a>=0 (number of open
// parens never drops below zero).
for(s=a=i=0;i<n;) // Loop from i=0 to n-1, note that we're
// traversing the bit field right-to-left.
a|= // a is the or-sum of all intermediate sums,
// it becomes negative whenever an intermediate
// sum is negative.
s+= // s is the number of closing parens minus the
// number of opening parens.
x>>i++&1 // Isolate current bit and inc i.
41-( ) // ASCII code of paren, a one bit
// yields 40 '(', a zero bit 41 ')'.
b[n-i]= // Store ASCII code in buffer.
2*( )-81; // 1 for ')' and -1 for '(' since
// we're going right-to-left.
}
C (gcc), 114 bytes
f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}
Try it online!
Should work for n <= 15.
Explanation
f(n,x,s,a,i){
char b[99]={}; // Output buffer initialized with zeros.
n*=2; // Double n.
for(x=1<<n;x--; // Loop from x=2**n-1 to 0, x is a bit field
// where 1 represents '(' and 0 represents ')'.
// This guarantees lexicographical order.
s|a<0||puts(b)) // Print buffer if s==0 (as many opening as
// closing parens) and a>=0 (number of open
// parens never drops below zero).
for(s=a=i=0;i<n;) // Loop from i=0 to n-1, note that we're
// traversing the bit field right-to-left.
a|= // a is the or-sum of all intermediate sums,
// it becomes negative whenever an intermediate
// sum is negative.
s+= // s is the number of closing parens minus the
// number of opening parens.
x>>i++&1 // Isolate current bit and inc i.
41-( ) // ASCII code of paren, a one bit
// yields 40 '(', a zero bit 41 ')'.
b[n-i]= // Store ASCII code in buffer.
2*( )-81; // 1 for ')' and -1 for '(' since
// we're going right-to-left.
}
edited Nov 6 at 19:59
answered Nov 6 at 18:53
nwellnhof
5,7081021
5,7081021
add a comment |
add a comment |
up vote
1
down vote
Perl 6, 42 bytes
{grep {!S:g/(<~~>*)//},[X~] <( )>xx$_*2}
Try it online!
Uses a recursive regex. Alternative substitution: S/[(<~~>)]*//
38 bytes with 0 and 1 as open/close symbols:
{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}
Try it online!
Explanation
{ } # Anonymous block
<( )> # List "(", ")"
xx$_*2 # repeated 2n times
[X~] # Cartesian product with string concat
# yields all strings of length 2n
# consisting of ( and )
grep { }, # Filter strings
S:g/ # Globally replace regex match
( # literal (
<~~> # whole regex matched recursively
* # zero or more times
) # literal )
// # with empty string
! # Is empty string?
add a comment |
up vote
1
down vote
Perl 6, 42 bytes
{grep {!S:g/(<~~>*)//},[X~] <( )>xx$_*2}
Try it online!
Uses a recursive regex. Alternative substitution: S/[(<~~>)]*//
38 bytes with 0 and 1 as open/close symbols:
{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}
Try it online!
Explanation
{ } # Anonymous block
<( )> # List "(", ")"
xx$_*2 # repeated 2n times
[X~] # Cartesian product with string concat
# yields all strings of length 2n
# consisting of ( and )
grep { }, # Filter strings
S:g/ # Globally replace regex match
( # literal (
<~~> # whole regex matched recursively
* # zero or more times
) # literal )
// # with empty string
! # Is empty string?
add a comment |
up vote
1
down vote
up vote
1
down vote
Perl 6, 42 bytes
{grep {!S:g/(<~~>*)//},[X~] <( )>xx$_*2}
Try it online!
Uses a recursive regex. Alternative substitution: S/[(<~~>)]*//
38 bytes with 0 and 1 as open/close symbols:
{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}
Try it online!
Explanation
{ } # Anonymous block
<( )> # List "(", ")"
xx$_*2 # repeated 2n times
[X~] # Cartesian product with string concat
# yields all strings of length 2n
# consisting of ( and )
grep { }, # Filter strings
S:g/ # Globally replace regex match
( # literal (
<~~> # whole regex matched recursively
* # zero or more times
) # literal )
// # with empty string
! # Is empty string?
Perl 6, 42 bytes
{grep {!S:g/(<~~>*)//},[X~] <( )>xx$_*2}
Try it online!
Uses a recursive regex. Alternative substitution: S/[(<~~>)]*//
38 bytes with 0 and 1 as open/close symbols:
{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}
Try it online!
Explanation
{ } # Anonymous block
<( )> # List "(", ")"
xx$_*2 # repeated 2n times
[X~] # Cartesian product with string concat
# yields all strings of length 2n
# consisting of ( and )
grep { }, # Filter strings
S:g/ # Globally replace regex match
( # literal (
<~~> # whole regex matched recursively
* # zero or more times
) # literal )
// # with empty string
! # Is empty string?
edited Nov 6 at 20:07
answered Nov 6 at 15:15
nwellnhof
5,7081021
5,7081021
add a comment |
add a comment |
up vote
0
down vote
Perl 5 -n
, 41 39 bytes
-2 bytes with angle brackets
s/<(?R)*>//gr||say for glob'{<,>}'x2x$_
Try it online!
Port of my Perl 6 answer.
add a comment |
up vote
0
down vote
Perl 5 -n
, 41 39 bytes
-2 bytes with angle brackets
s/<(?R)*>//gr||say for glob'{<,>}'x2x$_
Try it online!
Port of my Perl 6 answer.
add a comment |
up vote
0
down vote
up vote
0
down vote
Perl 5 -n
, 41 39 bytes
-2 bytes with angle brackets
s/<(?R)*>//gr||say for glob'{<,>}'x2x$_
Try it online!
Port of my Perl 6 answer.
Perl 5 -n
, 41 39 bytes
-2 bytes with angle brackets
s/<(?R)*>//gr||say for glob'{<,>}'x2x$_
Try it online!
Port of my Perl 6 answer.
edited Nov 6 at 16:40
answered Nov 6 at 16:05
nwellnhof
5,7081021
5,7081021
add a comment |
add a comment |
up vote
0
down vote
Jelly, 19 bytes
Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(
Try it online!
Output clarified over TIO.
add a comment |
up vote
0
down vote
Jelly, 19 bytes
Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(
Try it online!
Output clarified over TIO.
add a comment |
up vote
0
down vote
up vote
0
down vote
Jelly, 19 bytes
Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(
Try it online!
Output clarified over TIO.
Jelly, 19 bytes
Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(
Try it online!
Output clarified over TIO.
answered Nov 6 at 17:53
Erik the Outgolfer
30.3k428100
30.3k428100
add a comment |
add a comment |
up vote
0
down vote
Red, 214 184 bytes
func[n][p:""c: 2 ** d: 2 * n b: copyuntil[a: copy""e: c - 1 loop d[append a p/(e % 2 + 1)
e: e / 2]if not error? try[load a][append/only b a]1 > c: c - 1]foreach a sort b[print a]]
Try it online!
Uses Jo King's approach. Finds all possilble aarangements of brackes by base-2 convertion and then checks if the arrangement evaluates as a valid block.
add a comment |
up vote
0
down vote
Red, 214 184 bytes
func[n][p:""c: 2 ** d: 2 * n b: copyuntil[a: copy""e: c - 1 loop d[append a p/(e % 2 + 1)
e: e / 2]if not error? try[load a][append/only b a]1 > c: c - 1]foreach a sort b[print a]]
Try it online!
Uses Jo King's approach. Finds all possilble aarangements of brackes by base-2 convertion and then checks if the arrangement evaluates as a valid block.
add a comment |
up vote
0
down vote
up vote
0
down vote
Red, 214 184 bytes
func[n][p:""c: 2 ** d: 2 * n b: copyuntil[a: copy""e: c - 1 loop d[append a p/(e % 2 + 1)
e: e / 2]if not error? try[load a][append/only b a]1 > c: c - 1]foreach a sort b[print a]]
Try it online!
Uses Jo King's approach. Finds all possilble aarangements of brackes by base-2 convertion and then checks if the arrangement evaluates as a valid block.
Red, 214 184 bytes
func[n][p:""c: 2 ** d: 2 * n b: copyuntil[a: copy""e: c - 1 loop d[append a p/(e % 2 + 1)
e: e / 2]if not error? try[load a][append/only b a]1 > c: c - 1]foreach a sort b[print a]]
Try it online!
Uses Jo King's approach. Finds all possilble aarangements of brackes by base-2 convertion and then checks if the arrangement evaluates as a valid block.
edited Nov 6 at 19:08
answered Nov 6 at 15:22
Galen Ivanov
5,82711032
5,82711032
add a comment |
add a comment |
up vote
0
down vote
Retina 0.8.2, 50 bytes
.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)
Try it online! Uses <>
s. Explanation:
.+
$*
Convert to unary.
1
11
Double the result.
+%1`1
<$'¶$`>
Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to <>
.
Gm`^(?<-1>(<)*>)*$(?(1).)
Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.
add a comment |
up vote
0
down vote
Retina 0.8.2, 50 bytes
.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)
Try it online! Uses <>
s. Explanation:
.+
$*
Convert to unary.
1
11
Double the result.
+%1`1
<$'¶$`>
Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to <>
.
Gm`^(?<-1>(<)*>)*$(?(1).)
Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.
add a comment |
up vote
0
down vote
up vote
0
down vote
Retina 0.8.2, 50 bytes
.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)
Try it online! Uses <>
s. Explanation:
.+
$*
Convert to unary.
1
11
Double the result.
+%1`1
<$'¶$`>
Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to <>
.
Gm`^(?<-1>(<)*>)*$(?(1).)
Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.
Retina 0.8.2, 50 bytes
.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)
Try it online! Uses <>
s. Explanation:
.+
$*
Convert to unary.
1
11
Double the result.
+%1`1
<$'¶$`>
Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to <>
.
Gm`^(?<-1>(<)*>)*$(?(1).)
Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.
answered Nov 7 at 0:08
Neil
77.8k744174
77.8k744174
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175381%2fparentheses-sequences-in-lexicographical-order%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
Nov 6 at 14:12
Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
Nov 6 at 14:13
1
Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
Nov 6 at 14:23
3
Virtually the same, but with some weird restrictions like "You may not write recursive functions". /// A superset of this challenge (allow all Brain-Flak brackets)
– user202729
Nov 6 at 14:24
Does "an array, list or string" "of sequences" of "any open-close sign" mean we could output a list of lists of two integers (like
1
s and-1
s)?– Jonathan Allan
Nov 6 at 19:51