2009年12月25日星期五.sgu179
找一个合法的括号序列的下一个合法next_permutation
我打了个表，标*的为正确的排列。
我们发现在()()()()之后的都是非法序列,合法序列只占开始的一小部分。
然后我就用next_permutation水了一下，就过了
WindyWinter还介绍了一个找规律的方法: http://www.briefdream.com/sgu-179/
http://www.cppblog.com/schindlerlee/
/*
00001111 (((()))) *
00010111 ((()())) *
00011011 ((())()) *
00011101 ((()))() *
00011110 ((())))(
00100111 (()(())) *
00101011 (()()()) *
00101101 (()())() *
00101110 (()()))(
00110011 (())(()) *
00110101 (())()() *
00110110 (())())(
00111001 (()))(()
00111010 (()))()(
00111100 (())))((
01000111 ()((())) *
01001011 ()(()()) *
01001101 ()(())() *
01001110 ()(()))(
01010011 ()()(()) *
01010101 ()()()() *
01010110 ()()())(
01011001 ()())(()
01011010 ()())()(
01011100 ()()))((
01100011 ())((())
01100101 ())(()()
01100110 ())(())(
01101001 ())()(()
01101010 ())()()(
01101100 ())())((
01110001 ()))((()
01110010 ()))(()(
01110100 ()))()((
01111000 ())))(((
10000111 )(((()))
10001011 )((()())
10001101 )((())()
10001110 )((()))(
10010011 )(()(())
10010101 )(()()()
10010110 )(()())(
10011001 )(())(()
10011010 )(())()(
10011100 )(()))((
10100011 )()((())
10100101 )()(()()
10100110 )()(())(
10101001 )()()(()
10101010 )()()()(
10101100 )()())((
10110001 )())((()
10110010 )())(()(
10110100 )())()((
10111000 )()))(((
11000011 ))(((())
11000101 ))((()()
11000110 ))((())(
11001001 ))(()(()
11001010 ))(()()(
11001100 ))(())((
11010001 ))()((()
11010010 ))()(()(
11010100 ))()()((
11011000 ))())(((
11100001 )))(((()
11100010 )))((()(
11100100 )))(()((
11101000 )))()(((
11110000 ))))((((
*/
1 /*
2 * SOUR:sgu179
3 * ALGO:math
4 * DATE: 2009年 12月 25日 星期五 16:22:44 CST
5 * COMM:3 http://www.cppblog.com/schindlerlee/
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 typedef long long LL;
14 const int maxint = 0x7fffffff;
15 const long long max64 = 0x7fffffffffffffffll;
16
17 const int N = 10010;
18 char s[N], last[N];
19 int len;
20
21 int judge()
22 //1 right 0 false -1 exceed
23 {
24 int i;
25 for(i = 0;i < len ;i++) {
26 if(last[i] > s[i]) {
27 break;
28 }else if(last[i] < s[i]) {
29 return -1;
30 }
31 }
32 int top = 0;
33 for(int i = 0;i < len;i++) {
34 if(s[i] == '(') {
35 top ++;
36 }else {
37 if(top > 0)
38 top --;
39 else {
40 return 0;
41 }
42 }
43 }
44 return (top == 0);
45 }
46
47 int main()
48 {
49 int i,j,k;
50 scanf("%s",s);
51 len = strlen(s);
52 for(i = 0;i < len;i++) {
53 if(i & 1) {
54 last[i] = ')';
55 }else {
56 last[i] = '(';
57 }
58 }
59
60 next_permutation(s,s + len);
61 while(1) {
62 int r = judge();
63 if(r == 0) {
64 next_permutation(s,s + len);
65 }else if(r == 1) {
66 for(i = 0;i < len;i++) {
67 putchar(s[i]);
68 }
69 putchar(10);
70 break;
71 }else {
72 printf("No solution\n");
73 break;
74 }
75 }
76 return 0;
77 }
78
79
80