回答編集履歴
1
追記
answer
CHANGED
|
@@ -1,14 +1,16 @@
|
|
|
1
|
-
順列を再帰関数で生成するということでしょうか？
|
|
2
|
-
|
|
1
|
+
## ベースとなる考え方
|
|
3
2
|
|
|
3
|
+
順列を木で表現して、再帰関数で巡回します。
|
|
4
|
+
今回は LR の2文字なので、2分木と考えることができます。
|
|
5
|
+
|
|
4
6
|
3文字の例
|
|
5
7
|
|
|
6
8
|
|
|
7
9
|
文字数が木の深さになります。
|
|
8
10
|
|
|
11
|
+
```c
|
|
9
|
-
#
|
|
12
|
+
#include <stdio.h>
|
|
10
13
|
|
|
11
|
-
```c
|
|
12
14
|
/**
|
|
13
15
|
@brief func 順列を生成する再帰関数
|
|
14
16
|
@param depth ノードの深さ
|
|
@@ -34,4 +36,61 @@
|
|
|
34
36
|
char str[9] = {}; // str[8] は \0 終端用
|
|
35
37
|
func(0, str);
|
|
36
38
|
}
|
|
39
|
+
```
|
|
40
|
+
|
|
41
|
+
## 制約付きの順列
|
|
42
|
+
|
|
43
|
+
木の生成に関して、L 及び R の個数に制約をつけます。
|
|
44
|
+
|
|
45
|
+
```c
|
|
46
|
+
#include <stdio.h>
|
|
47
|
+
|
|
48
|
+
/**
|
|
49
|
+
@brief func 順列を生成する再帰関数
|
|
50
|
+
@param depth ノードの深さ
|
|
51
|
+
@param str 文字列を格納する変数
|
|
52
|
+
@param l_cnt L の残り個数
|
|
53
|
+
@param r_cnt R の残り個数
|
|
54
|
+
*/
|
|
55
|
+
void func(int depth, char str[], int l_cnt, int r_cnt)
|
|
56
|
+
{
|
|
57
|
+
if (l_cnt == 0 && r_cnt == 0) {
|
|
58
|
+
// L と R が残っていない場合
|
|
59
|
+
printf("%s\n", str);
|
|
60
|
+
return; // leaf ノード
|
|
61
|
+
}
|
|
62
|
+
|
|
63
|
+
if (l_cnt > 0) {
|
|
64
|
+
// L がまだ残っている場合
|
|
65
|
+
str[depth] = 'L';
|
|
66
|
+
func(depth + 1, str, l_cnt - 1, r_cnt);
|
|
67
|
+
}
|
|
68
|
+
|
|
69
|
+
if (r_cnt > 0) {
|
|
70
|
+
// R がまだ残っている場合
|
|
71
|
+
str[depth] = 'R';
|
|
72
|
+
func(depth + 1, str, l_cnt, r_cnt - 1);
|
|
73
|
+
}
|
|
74
|
+
}
|
|
75
|
+
|
|
76
|
+
int main()
|
|
77
|
+
{
|
|
78
|
+
char str[9] = {}; // str[8] は \0 終端用
|
|
79
|
+
int l_cnt = 3;
|
|
80
|
+
int r_cnt = 2;
|
|
81
|
+
func(0, str, l_cnt, r_cnt);
|
|
82
|
+
}
|
|
83
|
+
```
|
|
84
|
+
|
|
85
|
+
```output
|
|
86
|
+
LLLRR
|
|
87
|
+
LLRLR
|
|
88
|
+
LLRRL
|
|
89
|
+
LRLLR
|
|
90
|
+
LRLRL
|
|
91
|
+
LRRLL
|
|
92
|
+
RLLLR
|
|
93
|
+
RLLRL
|
|
94
|
+
RLRLL
|
|
95
|
+
RRLLL
|
|
37
96
|
```
|