Parentheses sequences in lexicographical order

Clash Royale CLAN TAG#URR8PPP

up vote
3
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

share|improve this question

edited 32 mins ago

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we use a different pair of parenthesises, e.g. ?
  – Jo King
  34 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
  – Luis felipe De jesus Munoz
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Eh, I can think of a few languages where eval would interpret them differently for example
  – Jo King
  31 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
  – user202729
  22 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  21 mins ago
  
  

  
  
  
  

add a comment | 

up vote
3
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

share|improve this question

edited 32 mins ago

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we use a different pair of parenthesises, e.g. ?
  – Jo King
  34 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
  – Luis felipe De jesus Munoz
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Eh, I can think of a few languages where eval would interpret them differently for example
  – Jo King
  31 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
  – user202729
  22 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  21 mins ago
  
  

  
  
  
  

add a comment | 

up vote
3
down vote

favorite

up vote
3
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

share|improve this question

edited 32 mins ago

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

^{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

code-golf

share|improve this question

edited 32 mins ago

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

share|improve this question

edited 32 mins ago

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

share|improve this question

share|improve this question

edited 32 mins ago

edited 32 mins ago

edited 32 mins ago

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

asked 41 mins ago

Luis felipe De jesus Munoz

3,54011049

3,54011049

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we use a different pair of parenthesises, e.g. ?
  – Jo King
  34 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
  – Luis felipe De jesus Munoz
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Eh, I can think of a few languages where eval would interpret them differently for example
  – Jo King
  31 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
  – user202729
  22 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  21 mins ago
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we use a different pair of parenthesises, e.g. ?
  – Jo King
  34 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
  – Luis felipe De jesus Munoz
  33 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Eh, I can think of a few languages where eval would interpret them differently for example
  – Jo King
  31 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
  – user202729
  22 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  21 mins ago
  
  

  
  
  
  

Can we use a different pair of parenthesises, e.g. ?
– Jo King
34 mins ago

Can we use a different pair of parenthesises, e.g. ?
– Jo King
34 mins ago

@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
33 mins ago

@JoKing Yes of course. I assume that wont make any difference anyway to the main concept of the challenge.
– Luis felipe De jesus Munoz
33 mins ago

Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
31 mins ago

Eh, I can think of a few languages where eval would interpret them differently for example
– Jo King
31 mins ago

Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
22 mins ago

Related: Catalan Numbers (result of that challenge = number of lines of result of this challenge)
– user202729
22 mins ago

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
21 mins ago

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
21 mins ago

add a comment | 

5 Answers
5

active

oldest

votes

up vote
3
down vote

Perl 6, 36 bytes

grep try !.EVAL,[X~] <[ ]>xx$_*2

Try it online!

Finds all lexographical combinations of $2n$ s and filters the ones that EVAL correctly. Note that is evaluated perfectly fine

share|improve this answer

answered 25 mins ago

Jo King

18.5k241100

add a comment | 

up vote
2
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

share|improve this answer

answered 15 mins ago

Kevin Cruijssen

33k554176

add a comment | 

up vote
1
down vote

Python 2, 91 88 84 bytes

f=lambda n:n and sorted(set(a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)))or['']

Try it online!

share|improve this answer

answered 18 mins ago

TFeld

12.9k2836

add a comment | 

up vote
1
down vote

JavaScript (ES6), 88 84 bytes

Returns an array.

n=>(g=(n,s='')=>n--?g(n,s+'()')&g(n,'()'+s)&g(n,`($s)`):g[s]=s)(n)||Object.keys(g)

Try it online!

share|improve this answer

edited 6 mins ago

answered 12 mins ago

Arnauld

67.4k584285

add a comment | 

up vote
0
down vote

Japt, 15 bytes

ç"" á Ôke"%

Try it

share

answered 4 mins ago

Shaggy

17.6k21663

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

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

Name Email

5 Answers
5

active

oldest

votes

5 Answers
5

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote

Perl 6, 36 bytes

grep try !.EVAL,[X~] <[ ]>xx$_*2

Try it online!

Finds all lexographical combinations of $2n$ s and filters the ones that EVAL correctly. Note that is evaluated perfectly fine

share|improve this answer

answered 25 mins ago

Jo King

18.5k241100

add a comment | 

up vote
3
down vote

Perl 6, 36 bytes

grep try !.EVAL,[X~] <[ ]>xx$_*2

Try it online!

Finds all lexographical combinations of $2n$ s and filters the ones that EVAL correctly. Note that is evaluated perfectly fine

share|improve this answer

answered 25 mins ago

Jo King

18.5k241100

add a comment | 

up vote
3
down vote

up vote
3
down vote

Perl 6, 36 bytes

grep try !.EVAL,[X~] <[ ]>xx$_*2

Try it online!

Finds all lexographical combinations of $2n$ s and filters the ones that EVAL correctly. Note that is evaluated perfectly fine

share|improve this answer

answered 25 mins ago

Jo King

18.5k241100

Perl 6, 36 bytes

grep try !.EVAL,[X~] <[ ]>xx$_*2

Try it online!

Finds all lexographical combinations of $2n$ s and filters the ones that EVAL correctly. Note that is evaluated perfectly fine

share|improve this answer

answered 25 mins ago

Jo King

18.5k241100

share|improve this answer

share|improve this answer

answered 25 mins ago

Jo King

18.5k241100

answered 25 mins ago

Jo King

18.5k241100

answered 25 mins ago

Jo King

18.5k241100

18.5k241100

add a comment | 

add a comment | 

up vote
2
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

share|improve this answer

answered 15 mins ago

Kevin Cruijssen

33k554176

add a comment | 

up vote
2
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

share|improve this answer

answered 15 mins ago

Kevin Cruijssen

33k554176

add a comment | 

up vote
2
down vote

up vote
2
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

share|improve this answer

answered 15 mins ago

Kevin Cruijssen

33k554176

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

share|improve this answer

answered 15 mins ago

Kevin Cruijssen

33k554176

share|improve this answer

share|improve this answer

answered 15 mins ago

Kevin Cruijssen

33k554176

answered 15 mins ago

Kevin Cruijssen

33k554176

answered 15 mins ago

Kevin Cruijssen

33k554176

33k554176

add a comment | 

add a comment | 

up vote
1
down vote

Python 2, 91 88 84 bytes

f=lambda n:n and sorted(set(a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)))or['']

Try it online!

share|improve this answer

answered 18 mins ago

TFeld

12.9k2836

add a comment | 

up vote
1
down vote

Python 2, 91 88 84 bytes

f=lambda n:n and sorted(set(a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)))or['']

Try it online!

share|improve this answer

answered 18 mins ago

TFeld

12.9k2836

add a comment | 

up vote
1
down vote

up vote
1
down vote

Python 2, 91 88 84 bytes

f=lambda n:n and sorted(set(a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)))or['']

Try it online!

share|improve this answer

answered 18 mins ago

TFeld

12.9k2836

Python 2, 91 88 84 bytes

f=lambda n:n and sorted(set(a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)))or['']

Try it online!

share|improve this answer

answered 18 mins ago

TFeld

12.9k2836

share|improve this answer

share|improve this answer

answered 18 mins ago

TFeld

12.9k2836

answered 18 mins ago

TFeld

12.9k2836

answered 18 mins ago

TFeld

12.9k2836

12.9k2836

add a comment | 

add a comment | 

up vote
1
down vote

JavaScript (ES6), 88 84 bytes

Returns an array.

n=>(g=(n,s='')=>n--?g(n,s+'()')&g(n,'()'+s)&g(n,`($s)`):g[s]=s)(n)||Object.keys(g)

Try it online!

share|improve this answer

edited 6 mins ago

answered 12 mins ago

Arnauld

67.4k584285

add a comment | 

up vote
1
down vote

JavaScript (ES6), 88 84 bytes

Returns an array.

n=>(g=(n,s='')=>n--?g(n,s+'()')&g(n,'()'+s)&g(n,`($s)`):g[s]=s)(n)||Object.keys(g)

Try it online!

share|improve this answer

edited 6 mins ago

answered 12 mins ago

Arnauld

67.4k584285

add a comment | 

up vote
1
down vote

up vote
1
down vote

JavaScript (ES6), 88 84 bytes

Returns an array.

n=>(g=(n,s='')=>n--?g(n,s+'()')&g(n,'()'+s)&g(n,`($s)`):g[s]=s)(n)||Object.keys(g)

Try it online!

share|improve this answer

edited 6 mins ago

answered 12 mins ago

Arnauld

67.4k584285

JavaScript (ES6), 88 84 bytes

Returns an array.

n=>(g=(n,s='')=>n--?g(n,s+'()')&g(n,'()'+s)&g(n,`($s)`):g[s]=s)(n)||Object.keys(g)

Try it online!

share|improve this answer

edited 6 mins ago

answered 12 mins ago

Arnauld

67.4k584285

share|improve this answer

share|improve this answer

edited 6 mins ago

edited 6 mins ago

edited 6 mins ago

answered 12 mins ago

Arnauld

67.4k584285

answered 12 mins ago

Arnauld

67.4k584285

answered 12 mins ago

Arnauld

67.4k584285

67.4k584285

add a comment | 

add a comment | 

up vote
0
down vote

Japt, 15 bytes

ç"" á Ôke"%

Try it

share

answered 4 mins ago

Shaggy

17.6k21663

add a comment | 

up vote
0
down vote

Japt, 15 bytes

ç"" á Ôke"%

Try it

share

answered 4 mins ago

Shaggy

17.6k21663

add a comment | 

up vote
0
down vote

up vote
0
down vote

Japt, 15 bytes

ç"" á Ôke"%

Try it

share

answered 4 mins ago

Shaggy

17.6k21663

Japt, 15 bytes

ç"" á Ôke"%

Try it

share

answered 4 mins ago

Shaggy

17.6k21663

share

share

answered 4 mins ago

Shaggy

17.6k21663

answered 4 mins ago

Shaggy

17.6k21663

answered 4 mins ago

Shaggy

17.6k21663

17.6k21663

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

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

Name Email

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

Name Email

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

Name Email

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

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email