並び変えの問題を総当たり表示 再帰で

Question

前提・実現したいこと

C言語で再帰の勉強をしています。初心者です。
入力されたLとRの個数（L＋R＜＝８）で考えられるLとRの並び順を再帰ですべて表示したいのですが
全く方法が思いつきません。
アドバイスいただけると幸いです。

＜入力例＞
L:3
R:2

＜出力例＞
LLLRR
LLRLR
LLRRL
LRRLL
LRLRL
LRLLR
RRLLL
RLRLL
RLLRL
RLLLR

発生している問題・エラーメッセージ

該当のソースコード

試したこと

補足情報（FW/ツールのバージョンなど）

Comments

[dice142]

記載された説明だけではどういう入力でどういう出力が得られれば期待通りなのかわかりません。入力例出力例もご提示ください。

[Ritsu]

ご指摘ありがとうございます

Answer 1

Cなど不要。そう、シェル芸ならね！

$ f(){ if [[ $1 == 0 && $2 == 0 ]];then echo $3;else [[ $1 > 0 ]]&&f $(($1 -1)) $2 ${3}L;[[ $2 > 0 ]]&&f $1 $(($2 -1)) ${3}R;fi };f 3 2
LLLRR
LLRLR
LLRRL
LRLLR
LRLRL
LRRLL
RLLLR
RLLRL
RLRLL
RRLLL

Answer 2

ベースとなる考え方

順列を木で表現して、再帰関数で巡回します。
今回は LR の2文字なので、2分木と考えることができます。

3文字の例

文字数が木の深さになります。

#include <stdio.h>

/**
   @brief func 順列を生成する再帰関数
   @param depth ノードの深さ
   @param str 文字列を格納する変数
 */
void func(int depth, char str[])
{
    if (depth == 8) {  // leaf ノード
        printf("%s\n", str);  // 文字列を表示する。
        return;
    }

    str[depth] = 'L';
    func(depth + 1, str);

    str[depth] = 'R';
    func(depth + 1, str);
}


int main()
{
    char str[9] = {};  // str[8] は \0 終端用
    func(0, str);
}

制約付きの順列

木の生成に関して、L 及び R の個数に制約をつけます。

#include <stdio.h>

/**
   @brief func 順列を生成する再帰関数
   @param depth ノードの深さ
   @param str 文字列を格納する変数
   @param l_cnt L の残り個数
   @param r_cnt R の残り個数
 */
void func(int depth, char str[], int l_cnt, int r_cnt)
{
    if (l_cnt == 0 && r_cnt == 0) {
        // L と R が残っていない場合
        printf("%s\n", str);
        return;  // leaf ノード
    }

    if (l_cnt > 0) {
        // L がまだ残っている場合
        str[depth] = 'L';
        func(depth + 1, str, l_cnt - 1, r_cnt);
    }

    if (r_cnt > 0) {
        // R がまだ残っている場合
        str[depth] = 'R';
        func(depth + 1, str, l_cnt, r_cnt - 1);
    }
}

int main()
{
    char str[9] = {};  // str[8] は \0 終端用
    int l_cnt = 3;
    int r_cnt = 2;
    func(0, str, l_cnt, r_cnt);
}

LLLRR
LLRLR
LLRRL
LRLLR
LRLRL
LRRLL
RLLLR
RLLRL
RLRLL
RRLLL

Comments

[Ritsu]

回答ありがとうございます。
図解もあって非常にわかりやすかったです。