$N^text{th}$ (in lexicographical order) term of balanced brackets string
$begingroup$
We have the following balanced brackets permutations of length $4cdot2$ in lexicographical order:
1. (((())))
2. ((()()))
3. ((())())
4. ((()))()
5. (()(()))
6. (()()())
7. (()())()
8. (())(())
9. (())()()
10. ()((()))
11. ()(()())
12. ()(())()
13. ()()(())
14. ()()()()
And I want to print for example 7th term which is: $(()())()$ without calculating 6 previous terms. Any ideas how to do it in $mathcal{O}(n)$ time? ($n$ = number of pairs of brackets)
I know that number of all these terms is $C(n)$ ($n^text{th}$ Catalan number) but it didn't help me with finding efficient algorithm.
Any hints will be helpful.
Edit: Provide yourself with more examples with this generator - https://ideone.com/5s4S3 .
permutations catalan-numbers
edited May 29 '13 at 16:10
Librecoin
2,385824
asked Aug 30 '12 at 2:08
user1user1
16317
$endgroup$
add a comment |
$begingroup$
We have the following balanced brackets permutations of length $4cdot2$ in lexicographical order:
1. (((())))
2. ((()()))
3. ((())())
4. ((()))()
5. (()(()))
6. (()()())
7. (()())()
8. (())(())
9. (())()()
10. ()((()))
11. ()(()())
12. ()(())()
13. ()()(())
14. ()()()()
And I want to print for example 7th term which is: $(()())()$ without calculating 6 previous terms. Any ideas how to do it in $mathcal{O}(n)$ time? ($n$ = number of pairs of brackets)
I know that number of all these terms is $C(n)$ ($n^text{th}$ Catalan number) but it didn't help me with finding efficient algorithm.
Any hints will be helpful.
Edit: Provide yourself with more examples with this generator - https://ideone.com/5s4S3 .
permutations catalan-numbers
edited May 29 '13 at 16:10
Librecoin
2,385824
asked Aug 30 '12 at 2:08
user1user1
16317
$endgroup$
$begingroup$
The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.
$endgroup$
– Gerry Myerson
Aug 30 '12 at 2:40
5
$begingroup$
This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
$endgroup$
– MJD
Aug 30 '12 at 3:02
$begingroup$
Thanks. It's called algorithm U and here it is: imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.
$endgroup$
– user1
Aug 31 '12 at 0:09
$begingroup$
Related question.
$endgroup$
– Librecoin
May 29 '13 at 16:10
add a comment |
$begingroup$
We have the following balanced brackets permutations of length $4cdot2$ in lexicographical order:
1. (((())))
2. ((()()))
3. ((())())
4. ((()))()
5. (()(()))
6. (()()())
7. (()())()
8. (())(())
9. (())()()
10. ()((()))
11. ()(()())
12. ()(())()
13. ()()(())
14. ()()()()
And I want to print for example 7th term which is: $(()())()$ without calculating 6 previous terms. Any ideas how to do it in $mathcal{O}(n)$ time? ($n$ = number of pairs of brackets)
I know that number of all these terms is $C(n)$ ($n^text{th}$ Catalan number) but it didn't help me with finding efficient algorithm.
Any hints will be helpful.
Edit: Provide yourself with more examples with this generator - https://ideone.com/5s4S3 .
permutations catalan-numbers
edited May 29 '13 at 16:10
Librecoin
2,385824
asked Aug 30 '12 at 2:08
user1user1
16317
$endgroup$
We have the following balanced brackets permutations of length $4cdot2$ in lexicographical order:
1. (((())))
2. ((()()))
3. ((())())
4. ((()))()
5. (()(()))
6. (()()())
7. (()())()
8. (())(())
9. (())()()
10. ()((()))
11. ()(()())
12. ()(())()
13. ()()(())
14. ()()()()
And I want to print for example 7th term which is: $(()())()$ without calculating 6 previous terms. Any ideas how to do it in $mathcal{O}(n)$ time? ($n$ = number of pairs of brackets)
I know that number of all these terms is $C(n)$ ($n^text{th}$ Catalan number) but it didn't help me with finding efficient algorithm.
Any hints will be helpful.
Edit: Provide yourself with more examples with this generator - https://ideone.com/5s4S3 .
permutations catalan-numbers
permutations catalan-numbers
edited May 29 '13 at 16:10
Librecoin
2,385824
asked Aug 30 '12 at 2:08
user1user1
16317
edited May 29 '13 at 16:10
Librecoin
2,385824
asked Aug 30 '12 at 2:08
user1user1
16317
edited May 29 '13 at 16:10
Librecoin
2,385824
edited May 29 '13 at 16:10
Librecoin
2,385824
edited May 29 '13 at 16:10
Librecoin
2,385824
2,385824
asked Aug 30 '12 at 2:08
user1user1
16317
asked Aug 30 '12 at 2:08
user1user1
16317
asked Aug 30 '12 at 2:08
user1user1
16317
16317
$begingroup$
The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.
$endgroup$
– Gerry Myerson
Aug 30 '12 at 2:40
5
$begingroup$
This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
$endgroup$
– MJD
Aug 30 '12 at 3:02
$begingroup$
Thanks. It's called algorithm U and here it is: imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.
$endgroup$
– user1
Aug 31 '12 at 0:09
$begingroup$
Related question.
$endgroup$
– Librecoin
May 29 '13 at 16:10
add a comment |
$begingroup$
The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.
$endgroup$
– Gerry Myerson
Aug 30 '12 at 2:40
5
$begingroup$
This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
$endgroup$
– MJD
Aug 30 '12 at 3:02
$begingroup$
Thanks. It's called algorithm U and here it is: imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.
$endgroup$
– user1
Aug 31 '12 at 0:09
$begingroup$
Related question.
$endgroup$
– Librecoin
May 29 '13 at 16:10
$begingroup$
The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.
$endgroup$
– Gerry Myerson
Aug 30 '12 at 2:40
$begingroup$
The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.
$endgroup$
– Gerry Myerson
Aug 30 '12 at 2:40
5
5
$begingroup$
This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
$endgroup$
– MJD
Aug 30 '12 at 3:02
$begingroup$
This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
$endgroup$
– MJD
Aug 30 '12 at 3:02
$begingroup$
Thanks. It's called algorithm U and here it is: imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.
$endgroup$
– user1
Aug 31 '12 at 0:09
$begingroup$
Thanks. It's called algorithm U and here it is: imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.
$endgroup$
– user1
Aug 31 '12 at 0:09
$begingroup$
Related question.
$endgroup$
– Librecoin
May 29 '13 at 16:10
$begingroup$
Related question.
$endgroup$
– Librecoin
May 29 '13 at 16:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is an implementation of Algorithm-U in Java. However, I have simply subtracted $N$ from $C(n)$.
public static String genNthBalParStr(int numPairs, int N) {
int q, p, c, c1, m;
String str = "";
q = numPairs;
m = p = c = 1;
while (p < numPairs) {
p = p + 1;
c = ((4 * p - 2) * c)/(p + 1);
}
N = c - (N - 1);
while (true) {
if (q != 0) {
c1 = ((q + 1) * (q - p) * c)/((q + p) * (q - p + 1));
if (N > c1) {
p = p - 1;
c = c - c1;
N = N - c1;
str += "(";
m = m + 1;
}
else {
q = q - 1;
c = c1;
str += ")";
m = m + 1;
}
}
else break;
}
return str;
}
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
$endgroup$
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.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f188634%2fn-textth-in-lexicographical-order-term-of-balanced-brackets-string%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is an implementation of Algorithm-U in Java. However, I have simply subtracted $N$ from $C(n)$.
public static String genNthBalParStr(int numPairs, int N) {
int q, p, c, c1, m;
String str = "";
q = numPairs;
m = p = c = 1;
while (p < numPairs) {
p = p + 1;
c = ((4 * p - 2) * c)/(p + 1);
}
N = c - (N - 1);
while (true) {
if (q != 0) {
c1 = ((q + 1) * (q - p) * c)/((q + p) * (q - p + 1));
if (N > c1) {
p = p - 1;
c = c - c1;
N = N - c1;
str += "(";
m = m + 1;
}
else {
q = q - 1;
c = c1;
str += ")";
m = m + 1;
}
}
else break;
}
return str;
}
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
$endgroup$
add a comment |
$begingroup$
Here is an implementation of Algorithm-U in Java. However, I have simply subtracted $N$ from $C(n)$.
public static String genNthBalParStr(int numPairs, int N) {
int q, p, c, c1, m;
String str = "";
q = numPairs;
m = p = c = 1;
while (p < numPairs) {
p = p + 1;
c = ((4 * p - 2) * c)/(p + 1);
}
N = c - (N - 1);
while (true) {
if (q != 0) {
c1 = ((q + 1) * (q - p) * c)/((q + p) * (q - p + 1));
if (N > c1) {
p = p - 1;
c = c - c1;
N = N - c1;
str += "(";
m = m + 1;
}
else {
q = q - 1;
c = c1;
str += ")";
m = m + 1;
}
}
else break;
}
return str;
}
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
$endgroup$
add a comment |
$begingroup$
Here is an implementation of Algorithm-U in Java. However, I have simply subtracted $N$ from $C(n)$.
public static String genNthBalParStr(int numPairs, int N) {
int q, p, c, c1, m;
String str = "";
q = numPairs;
m = p = c = 1;
while (p < numPairs) {
p = p + 1;
c = ((4 * p - 2) * c)/(p + 1);
}
N = c - (N - 1);
while (true) {
if (q != 0) {
c1 = ((q + 1) * (q - p) * c)/((q + p) * (q - p + 1));
if (N > c1) {
p = p - 1;
c = c - c1;
N = N - c1;
str += "(";
m = m + 1;
}
else {
q = q - 1;
c = c1;
str += ")";
m = m + 1;
}
}
else break;
}
return str;
}
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
$endgroup$
Here is an implementation of Algorithm-U in Java. However, I have simply subtracted $N$ from $C(n)$.
public static String genNthBalParStr(int numPairs, int N) {
int q, p, c, c1, m;
String str = "";
q = numPairs;
m = p = c = 1;
while (p < numPairs) {
p = p + 1;
c = ((4 * p - 2) * c)/(p + 1);
}
N = c - (N - 1);
while (true) {
if (q != 0) {
c1 = ((q + 1) * (q - p) * c)/((q + p) * (q - p + 1));
if (N > c1) {
p = p - 1;
c = c - c1;
N = N - c1;
str += "(";
m = m + 1;
}
else {
q = q - 1;
c = c1;
str += ")";
m = m + 1;
}
}
else break;
}
return str;
}
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
edited Aug 19 '15 at 4:32
user147263
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
answered Nov 3 '13 at 3:09
Arghya Kusum DasArghya Kusum Das
1
1
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f188634%2fn-textth-in-lexicographical-order-term-of-balanced-brackets-string%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.
$endgroup$
– Gerry Myerson
Aug 30 '12 at 2:40
5
$begingroup$
This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
$endgroup$
– MJD
Aug 30 '12 at 3:02
$begingroup$
Thanks. It's called algorithm U and here it is: imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.
$endgroup$
– user1
Aug 31 '12 at 0:09
$begingroup$
Related question.
$endgroup$
– Librecoin
May 29 '13 at 16:10