回答編集履歴
1
追記
test
CHANGED
|
@@ -1,6 +1,10 @@
|
|
|
1
|
-
|
|
1
|
+
## ベースとなる考え方
|
|
2
2
|
|
|
3
|
+
|
|
4
|
+
|
|
5
|
+
順列を木で表現して、再帰関数で巡回します。
|
|
6
|
+
|
|
3
|
-
|
|
7
|
+
今回は LR の2文字なので、2分木と考えることができます。
|
|
4
8
|
|
|
5
9
|
|
|
6
10
|
|
|
@@ -14,11 +18,11 @@
|
|
|
14
18
|
|
|
15
19
|
|
|
16
20
|
|
|
21
|
+
```c
|
|
22
|
+
|
|
17
|
-
#
|
|
23
|
+
#include <stdio.h>
|
|
18
24
|
|
|
19
25
|
|
|
20
|
-
|
|
21
|
-
```c
|
|
22
26
|
|
|
23
27
|
/**
|
|
24
28
|
|
|
@@ -71,3 +75,117 @@
|
|
|
71
75
|
}
|
|
72
76
|
|
|
73
77
|
```
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
## 制約付きの順列
|
|
82
|
+
|
|
83
|
+
|
|
84
|
+
|
|
85
|
+
木の生成に関して、L 及び R の個数に制約をつけます。
|
|
86
|
+
|
|
87
|
+
|
|
88
|
+
|
|
89
|
+
```c
|
|
90
|
+
|
|
91
|
+
#include <stdio.h>
|
|
92
|
+
|
|
93
|
+
|
|
94
|
+
|
|
95
|
+
/**
|
|
96
|
+
|
|
97
|
+
@brief func 順列を生成する再帰関数
|
|
98
|
+
|
|
99
|
+
@param depth ノードの深さ
|
|
100
|
+
|
|
101
|
+
@param str 文字列を格納する変数
|
|
102
|
+
|
|
103
|
+
@param l_cnt L の残り個数
|
|
104
|
+
|
|
105
|
+
@param r_cnt R の残り個数
|
|
106
|
+
|
|
107
|
+
*/
|
|
108
|
+
|
|
109
|
+
void func(int depth, char str[], int l_cnt, int r_cnt)
|
|
110
|
+
|
|
111
|
+
{
|
|
112
|
+
|
|
113
|
+
if (l_cnt == 0 && r_cnt == 0) {
|
|
114
|
+
|
|
115
|
+
// L と R が残っていない場合
|
|
116
|
+
|
|
117
|
+
printf("%s\n", str);
|
|
118
|
+
|
|
119
|
+
return; // leaf ノード
|
|
120
|
+
|
|
121
|
+
}
|
|
122
|
+
|
|
123
|
+
|
|
124
|
+
|
|
125
|
+
if (l_cnt > 0) {
|
|
126
|
+
|
|
127
|
+
// L がまだ残っている場合
|
|
128
|
+
|
|
129
|
+
str[depth] = 'L';
|
|
130
|
+
|
|
131
|
+
func(depth + 1, str, l_cnt - 1, r_cnt);
|
|
132
|
+
|
|
133
|
+
}
|
|
134
|
+
|
|
135
|
+
|
|
136
|
+
|
|
137
|
+
if (r_cnt > 0) {
|
|
138
|
+
|
|
139
|
+
// R がまだ残っている場合
|
|
140
|
+
|
|
141
|
+
str[depth] = 'R';
|
|
142
|
+
|
|
143
|
+
func(depth + 1, str, l_cnt, r_cnt - 1);
|
|
144
|
+
|
|
145
|
+
}
|
|
146
|
+
|
|
147
|
+
}
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
151
|
+
int main()
|
|
152
|
+
|
|
153
|
+
{
|
|
154
|
+
|
|
155
|
+
char str[9] = {}; // str[8] は \0 終端用
|
|
156
|
+
|
|
157
|
+
int l_cnt = 3;
|
|
158
|
+
|
|
159
|
+
int r_cnt = 2;
|
|
160
|
+
|
|
161
|
+
func(0, str, l_cnt, r_cnt);
|
|
162
|
+
|
|
163
|
+
}
|
|
164
|
+
|
|
165
|
+
```
|
|
166
|
+
|
|
167
|
+
|
|
168
|
+
|
|
169
|
+
```output
|
|
170
|
+
|
|
171
|
+
LLLRR
|
|
172
|
+
|
|
173
|
+
LLRLR
|
|
174
|
+
|
|
175
|
+
LLRRL
|
|
176
|
+
|
|
177
|
+
LRLLR
|
|
178
|
+
|
|
179
|
+
LRLRL
|
|
180
|
+
|
|
181
|
+
LRRLL
|
|
182
|
+
|
|
183
|
+
RLLLR
|
|
184
|
+
|
|
185
|
+
RLLRL
|
|
186
|
+
|
|
187
|
+
RLRLL
|
|
188
|
+
|
|
189
|
+
RRLLL
|
|
190
|
+
|
|
191
|
+
```
|