ベースとなる考え方
順列を木で表現して、再帰関数で巡回します。
今回は LR の2文字なので、2分木と考えることができます。
3文字の例
文字数が木の深さになります。
c
1#include <stdio.h>
2
3/**
4 @brief func 順列を生成する再帰関数
5 @param depth ノードの深さ
6 @param str 文字列を格納する変数
7 */
8void func(int depth, char str[])
9{
10 if (depth == 8) { // leaf ノード
11 printf("%s\n", str); // 文字列を表示する。
12 return;
13 }
14
15 str[depth] = 'L';
16 func(depth + 1, str);
17
18 str[depth] = 'R';
19 func(depth + 1, str);
20}
21
22
23int main()
24{
25 char str[9] = {}; // str[8] は \0 終端用
26 func(0, str);
27}
制約付きの順列
木の生成に関して、L 及び R の個数に制約をつけます。
c
1#include <stdio.h>
2
3/**
4 @brief func 順列を生成する再帰関数
5 @param depth ノードの深さ
6 @param str 文字列を格納する変数
7 @param l_cnt L の残り個数
8 @param r_cnt R の残り個数
9 */
10void func(int depth, char str[], int l_cnt, int r_cnt)
11{
12 if (l_cnt == 0 && r_cnt == 0) {
13 // L と R が残っていない場合
14 printf("%s\n", str);
15 return; // leaf ノード
16 }
17
18 if (l_cnt > 0) {
19 // L がまだ残っている場合
20 str[depth] = 'L';
21 func(depth + 1, str, l_cnt - 1, r_cnt);
22 }
23
24 if (r_cnt > 0) {
25 // R がまだ残っている場合
26 str[depth] = 'R';
27 func(depth + 1, str, l_cnt, r_cnt - 1);
28 }
29}
30
31int main()
32{
33 char str[9] = {}; // str[8] は \0 終端用
34 int l_cnt = 3;
35 int r_cnt = 2;
36 func(0, str, l_cnt, r_cnt);
37}
output
1LLLRR
2LLRLR
3LLRRL
4LRLLR
5LRLRL
6LRRLL
7RLLLR
8RLLRL
9RLRLL
10RRLLL