【C言語】組み合わせの全パターンを列挙する

このページでは、C言語で「組み合わせの全パターンを列挙」する方法について解説していきます。

といっても、全探索（総当たり）でパターンを見つけるだけなので処理速度は遅いです。ですが、全探索や再帰呼び出しについての理解も深まると思いますので、とにかく組み合わせの全パターンを列挙したいような場合や全探索について復習したいというような方は是非読んでみてください。

さて、組み合わせとは「n 個の区別可能な要素の中から r 個選んだ時に、順序を区別せずに選んだ要素を並べたもの」のことです。

例えば A・B・C・D・E の英字が書かれた 5 枚のカードの山から 3 枚のカードを選ぶ場合は、n = 5、r = 3 となります。

選んだカードが１枚目から順に A・B・D だった場合、この A・B・D が１つの組み合わせのパターンとなります。

もし選んだカードが１枚目から順に B・D・A だった場合、順序は異なりますが、手元にあるカードは A・B・D の組み合わせのパターンと同じですので、これらの２つは同じ組み合わせのパターンとなります。

こんな感じで順序を区別しなかった場合、5 枚のカードの山から 3 枚のカードを（重複なしで）選んだ際に、組み合わせとして存在するパターンの全ては下記の 10 個となります。

• C D E
• B D E
• B C E
• B C D
• A D E
• A C E
• A C D
• A B E
• A B D
• A B C

今回は、n と r を引数で指定した際に、 n 個の要素の中から r 個選んだ時に取りうる全パターンを列挙（表示）する関数の実現方法について考えていきます。

また、組み合わせは「重複なし」の場合と「重複あり」の場合とで求め方が異なります。

先程の例で考えるとカードを選んだ際、選んだカードを山に戻さなければ選んだカードが重複することはありません。その一方で、毎回カードを選んだ後に山に戻すようにした場合、選んだカードが重複する可能性があります。例えば３枚のカード全てが B だという場合もあり得ますね！

今回は、この重複なしの場合の組み合わせのパターンの全列挙を行う方法について解説した後に、重複ありの場合のパターンの全列挙を行う方法についても解説していきたいと思います。

組み合わせの全パターンを列挙する（重複なし）

それでは、組み合わせの全パターンを列挙する方法について解説していきます。まず選ぶ要素に重複がない場合の組み合わせの全パターンの列挙について解説していきます。

重複なしで組み合わせの全パターンを列挙する考え方

今回は、全探索で組み合わせの全パターンを列挙していきたいと思います。

全探索とは一言で言えば、全てのパターンを洗い出し、その中から条件に合致するパターンを見つけだす方法となります。

まず、重複なしの場合、１つ１つの要素に対して行われる操作は下記の２つのどちらかとなります。

• 選ぶ
• 選ばない

要素が n 個あるわけですから、その n 個の要素それぞれにおいて、上記の２つのうちのどちらかの操作が行われることになります。そのため、n 個の各要素に対して行われる操作の全パターン数は 2 の n 乗 個となります。

例えば 3 枚のカードで考えれば、下図が各カードを “選ぶ” or “選ばない” の全てのパターンを網羅した表となります。 2 の 3 乗 の 8 パターン存在することが確認できると思います。

前述の通り、重複無しの場合、n 個の要素から要素を選ぶときのパターンは 2 の n 乗 個のパターン存在します。

ただし、これらのパターン全てが組み合わせの全パターンというわけではありません。なぜなら要素を選ぶ個数が考慮されていないからです。この「選ぶ個数」こそが、n 個の要素から r 個の要素を選んだ際の組み合わせのパターンとなる条件となります。

つまり、n 個の要素から要素を選ぶときの全パターンのうち、「r 個のみ “選ぶ” になっている」という条件を満たしているパターンのみが、n 個の要素から r 個の要素を選んだ際の組み合わせのパターンとなります。

例えば先ほどの 3 枚のカードの例であれば、3 枚のカードの中から 2 枚を選んだ際の組み合わせの全パターンは、下の図の青枠で示す、”選ぶ” になっているカードが 2 枚であるパターンのみとなります。

したがって、この場合に列挙する組み合わせのパターンは下記の３つとなります。

• B C
• A C
• A B

同様に、3 枚のカードの中から 1 枚を選んだ際の組み合わせの全パターンは、下の図の青枠で示すパターンとなります。

したがって、この場合に列挙する組み合わせのパターンは下記の３つとなります。

• C
• B
• A

要は、n 個の要素から要素を選ぶときの全パターンを作り出し、その中から「r 個のみ “選ぶ” パターン」となっているものを表示してやれば、n 個の要素から r 個選ぶ際の組み合わせの全パターンを列挙することが出来ます。

スポンサーリンク

ループで組み合わせを全列挙する関数（重複なし）

ここまでの解説に基づいて作成した、全探索で n = 5 個の要素から r 個の要素を選ぶ際の組み合わせの全パターンを列挙するプログラムのソースコードは下記のようになります。

combination が、要素数 n = 5 個の配列 elems の中から r 個の要素を選ぶ際の組み合わせの全パターンを列挙する関数になります（要素数 n は 5 であることを前提とした関数となっています。理由は後述で説明します）。

#include <stdio.h>

#define N 5
#define R 3

void printCombination(int pattern[], char elems[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < pattern[i]; j++)
            printf("%c ", elems[i]);
    }
    printf("\n");
}

int getNumSelected(int pattern[], int n) {
    /* "選ぶ"と決定された要素の数を計算 */
    
    int num_selected = 0;
    for (int i = 0; i < n; i++) {
        num_selected += pattern[i];
    }

    return num_selected;
}

/* n個の要素からr個の要素を選ぶ場合の全パターンを列挙する */
void combination(int pattern[], char elems[], int n, int r) {

    for (int a = 0; a <= 1; a++) {
        /* 第0個目の要素の"選ぶ"or"選ばない"を決定 */
        pattern[0] = a;
        for (int b = 0; b <= 1; b++) {
            /* 第1個目の要素の"選ぶ"or"選ばない"を決定 */
            pattern[1] = b;
            for (int c = 0; c <= 1; c++) {
                /* 第2個目の要素の"選ぶ"or"選ばない"を決定 */
                pattern[2] = c;
                for (int d = 0; d <= 1; d++) {
                    /* 第3個目の要素の"選ぶ"or"選ばない"を決定 */
                    pattern[3] = d;
                    for (int e = 0; e <= 1; e++) {
                        /* 第4個目の要素の"選ぶ"or"選ばない"を決定 */
                        pattern[4] = e;

                        /* "選ぶ"と決定された要素の数がrの場合のみパターンを表示 */
                        if (getNumSelected(pattern, n) == r) {
                            printCombination(pattern, elems, n);
                        }
                    }
                }
            }
        }
    }

}

int main(void) {
    char elems[N];

    int pattern[N] = {0};

    for (int i = 0; i < N; i++) {
        elems[i] = 'A' + i;
    }

    combination(pattern, elems, N, R);
}

elems が選ぶ対象となる要素が格納された配列であり、 A・B・C・D・E の 5 つが格納されています。上記を実行すると、elems から 3 つの要素を選ぶ際の組み合わせの全パターンが下記のように表示されます。

C D E 
B D E 
B C E 
B C D 
A D E 
A C E 
A C D 
A B E 
A B D 
A B C 

配列 pattern は、配列 elems の中の各要素が “選ぶ” or “選ばない” のどちらに決定されたかを管理する配列になります。pattern[i] が 0 の時、elems[i] を “選ばない” と決定されたことを表し、pattern[i] が 1 の時、elems[i] の要素を “選ぶ” と決定されたことを表します。

したがって、5 個の要素から要素を選ぶときの全パターンは、配列 pattern が 00000 〜 11111 の 32 個（2 の 5 乗 個）ということになります。

このパターンを生成しているのが、combination 関数における a 〜 e に対する 5 重ループになります。外側のループから順に pattern の先頭側の要素の値を 0 〜 1 に変化させるようにすることで、配列 pattern が 00000 〜 11111 の間で変化するようにしています。

さらに、この pattern の全要素を足し合わせた結果を getNumSelected 関数で取得し、その取得した個数が「選ぶ個数」を示す r と一致するかどうかの判断を行なっています。

一致するということは、r 個の要素のみが選ばれたことを意味しますので、この時の pattern は 5 個の要素の中から r 個選んだ時のパターンの１つということになります。

そのため、この場合は printCombination 関数を実行し、”選ぶ” と決定された elems の要素を１つのパターンとして表示するようにしています。

上記のように動作しているため、combination 関数は 5 個の要素から r 個の要素を選ぶ際の組み合わせの全パターンを列挙することが出来ます。

printCombination 関数について補足しておくと、この関数では i に対するループの中で elems[i] の要素を pattern[i] 回連続して表示する処理を行なっています。これにより、１つのパターンの表示を行なっています。

今回は pattern[i] に 0 or 1 の値のみが格納されており、1 の場合、つまり elems[i] を “選ぶ” と決定している場合のみ elems[i] が 1 回表示されるようになっています。

ちょっとややこしい作りになっていますが、これは後述で解説する「重複あり」の場合にも printCombination 関数を使い回せるようにするためです。

再帰呼び出しで組み合わせを全列挙する関数（重複なし）

先ほど紹介した combination 関数では 5 重ループを組む必要があり、非常に関数が読みづらくなっています。また、今回は n = 5 としているため 5 重ループで済んでいますが、n の値に応じて n 重のループを組んで処理を行う必要があります。

つまり、上記の combination 関数は n = 5 であることを前提とした作りとなってしまっています。上記のように単純なループで全探索を行う場合、n の値を変更するためには、n の値に応じてループの数を変更する必要があります。n が変わるたびにソースコードを変更することになるので面倒です。

それを解決する１つの手段が再帰呼び出しの利用です。再帰呼び出しとは関数の中でその関数自身を呼び出すことであり、この再帰呼び出しを利用した場合、全探索で n 個の要素から r 個の要素を選ぶ際の組み合わせの全パターンを列挙するプログラムのソースコードは下記のように書くことが出来ます。

#include <stdio.h>

#define N 5
#define R 3

void printCombination(int pattern[], char elems[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < pattern[i]; j++)
            printf("%c ", elems[i]);
    }
    printf("\n");
}

int getNumSelected(int pattern[], int n) {
    /* "選ぶ"と決定された要素の数を計算 */
    
    int num_selected = 0;
    for (int i = 0; i < n; i++) {
        num_selected += pattern[i];
    }

    return num_selected;
}

/* n個の要素からr個の要素を選ぶ場合の全パターンを列挙する */
void combination(int pattern[], char elems[], int n, int r, int num_decided) {

    int num_selected = getNumSelected(pattern, num_decided);

    if (num_decided == n) {
        /* n個全ての要素に対して"選ぶ"or"選ばない"が決定ずみ */
        if (num_selected == r) {
            /* r個だけ選ばれている場合のみ、選ばれた要素を表示 */
            printCombination(pattern, elems, n);
        }
        return;
    }

    /* num_decided個目の要素を"選ばない"場合のパターンを作成 */
    pattern[num_decided] = 0;
    combination(pattern, elems, n, r, num_decided + 1);

    /* num_decided個目の要素を"選ぶ"場合のパターンを作成 */
    pattern[num_decided] = 1;
    combination(pattern, elems, n, r, num_decided + 1);
}

int main(void) {
    char elems[N];

    int pattern[N] = {0};

    for (int i = 0; i < N; i++) {
        elems[i] = 'A' + i;
    }

    combination(pattern, elems, N, R, 0);
}

先ほどと同様に、combination が要素数 n 個の配列 elems の中から r 個の要素を選ぶ際の組み合わせの全パターンを列挙する関数になります。ループで組み合わせを全列挙する関数（重複なし） で紹介した combination 関数に比べ、ループが無くなりスッキリした印象を受けるのではないかと思います。

上記の combination 関数においても、引数 pattern・elems・n・r の意味合いは ループで組み合わせを全列挙する関数（重複なし） で示した combination 関数と同様です。また、実行結果においても、下記のように先ほどの場合と同じ結果を得ることが出来ます。

C D E 
B D E 
B C E 
B C D 
A D E 
A C E 
A C D 
A B E 
A B D 
A B C

引数 num_decided は “選ぶ” or “選ばない” を決定した要素数を表しており、pattern[num_decided] に 0 or 1 を格納することで、まだ “選ぶ” or “選ばない” が決定されていない要素のうちの先頭の要素の “選ぶ” or “選ばない” が決定されることになります。

さらに、その決定後に combination(pattern, elems, n, r, num_decided + 1) を実行することで、引数 num_decided が +1 されて再度同様の処理が実行されます。そのため、次の要素の “選ぶ” or “選ばない” が決定されて再び combination(pattern, elems, n, r, num_decided + 1) が実行されることになります。

ですので、combination 関数を最初に実行する際に引数 num_decided に 0 を指定しておけば、上記の処理が繰り返し実行され、pattern の先頭要素から順に、どんどん要素の “選ぶ” or “選ばない” が決定されていくことになります。

また、下記のように、combination 関数の中では pattern[num_decided] に 0 を格納した後と、pattern[num_decided] に 1 を格納した後の両方で combination 関数の再帰呼び出しを行なっています。

/* num_decided個目の要素を"選ばない"場合のパターンを作成 */
pattern[num_decided] = 0;
combination(pattern, elems, n, r, num_decided + 1);

/* num_decided個目の要素を"選ぶ"場合のパターンを作成 */
pattern[num_decided] = 1;
combination(pattern, elems, n, r, num_decided + 1);

そのため、下の図のように枝分かれしながら pattern に 0 or 1 の値が格納されていく感じで処理が進んでいくことになります（図は n = 3 の場合のものです）。矢印が combination 関数の呼び出しの流れを示しています。

また、num_decided が n と一致する場合、これは全ての要素の “選ぶ” or “選ばない” が決定済みである、すなわち１つのパターンが作成されたことを意味します。ですので、この場合は pattern の中の 1 の個数が「選ぶ個数」を表す r と一致するかを調べ（getNumSelected は pattern の全要素の和を返却する関数）、一致する場合は printCombination でパターンの表示を行うようにしています。

さらに、この場合は全ての要素の “選ぶ” or “選ばない” が決定済みであり、もう新たな要素の “選ぶ” or “選ばない” を決める必要はないので、combination 関数の再帰呼び出しは行わないようにしています。

この辺りの処理を行なっているのは、combination 関数の下記部分になります。num_decided が n と一致する場合は return が実行されるため、再帰呼び出しを行うことなく関数が終了することになります。

int num_selected = getNumSelected(pattern, num_decided);

if (num_decided == n) {
    /* n個全ての要素に対して"選ぶ"or"選ばない"が決定ずみ */
    if (num_selected == r) {
        /* r個だけ選ばれている場合のみ、選ばれた要素を表示 */
        printCombination(pattern, elems, n);
    }
    return;
}

for ループで明示的に繰り返しは行なっていませんが、再帰呼び出しにより combination が繰り返し実行されるので、全パターンの作成を行うことが出来ています。

ただ、for ループの場合とは異なり、要素数を変更する場合にループ文を組み直すようなことを行う必要はなく、最初に実行する combination 関数の引数 n に変更後の要素数を指定するだけで、要素数を変更した場合の組み合わせのパターンの列挙を行うことが可能です（n が幾つであろうと num_decided が n と一致した場合に再帰呼び出しを行わないようになっている）。

実際に、ソースコード先頭付近における下記の define 部分を変更すれば、変更後の N と R に対して、N 個の要素から R 個の要素を選ぶ際の組み合わせの全パターンを列挙することが出来ます。

#define N 5
#define R 3

ただし、N を大きくすると作成するパターン数が大きくなりすぎてプログラムが終わらなくなるので注意してください。特に今回は全探索を行なっているので処理速度は遅いです。

バックトラックで組み合わせを全列挙する関数（重複なし）

ここまで単純に全探索を行なって組み合わせの全パターンを見つけてきました。

今度は、ちょっとだけ工夫をして単なる全探索よりも処理効率を良くしていきたいと思います。

全探索の場合、例えば 3 つの要素の中から 1 つの要素を選ぶ際の組み合わせの全パターン列挙するためには、まずは 3 つの要素から要素を選ぶ際の全パターンを作成する必要がありました。

再帰呼び出しで組み合わせを全列挙する関数（重複なし） においては、下図のように、pattern に格納する値を枝分かれさせながら再帰呼び出しを繰り返すことでパターンの作成を行いました。

ここで、選ぶ要素の数が 1 つであることを考えると、一番右の下から２つのパターンに関しては再帰呼び出しを行なってパターンを作るまでもなく、求める組み合わせのパターンになり得ないことがわかります。なぜなら、再帰呼び出しを行う前に既に pattern 内に存在する 1 の数（”選ぶ” と決定した要素の数）が 1 を超えているからです。

したがって、このパターンを作成するための再帰呼び出しは不要で、再帰呼び出ししないようにすることで処理量を減らすことが出来ます。

また、選ぶ要素の個数が 2 つである場合、一番右の上から２つのパターンに関しては再帰呼び出しを行なってパターンを作るまでもなく、求める組み合わせのパターンになり得ないことがわかります。なぜなら、再帰呼び出しを行う前に pattern 内に存在する 1 の数（”選ぶ” と決定した要素の数）が 0 であり、残りの１つの要素を “選ぶ” or “選ばない” に関わらず絶対に 2 にならないからです。

したがって、このパターンを作成するための再帰呼び出しは不要で、再帰呼び出ししないようにすることで処理量を減らすことが出来ます。

こんな感じで、パターンを作成している途中で、求める組み合わせのパターンになり得ないことが明らかになる場合があります。こういった際に、再帰呼び出しを継続して行うのではなく、一手戻して他のパターンの作成を試すようにすることで、処理効率を向上させることが出来ます。

このように、途中で求めたいパターンになり得ないと分かった際に一手戻して他のパターンの作成を試みるような手法をバックトラック法と呼びます。

このバックトラック法を用いた場合、再帰呼び出しで組み合わせを全列挙する関数（重複なし） で紹介した関数 combination は下記のように変更することが出来ます。

/* n個の要素からr個の要素を選ぶ場合の全パターンを列挙する */
void combination(int pattern[], char elems[], int n, int r, int num_decided) {

    int num_selected = getNumSelected(pattern, num_decided);

    if (num_decided == n) {
        /* n個全ての要素に対して"選ぶ"or"選ばない"が決定ずみ */
        if (num_selected == r) {
            /* r個だけ選ばれている場合のみ、選ばれた要素を表示 */
            printCombination(pattern, elems, n);
        }
        return;
    }

    if (num_selected > r) {
        /* 既にrを超えて選んでいる場合 */
        return;
    }

    if (r - num_selected > n - num_decided) {
        /* r個選ぶのに要素の数が足りない場合 */
        return;
    }

    /* num_decided個目の要素を"選ばない"場合のパターンを作成 */
    pattern[num_decided] = 0;
    combination(pattern, elems, n, r, num_decided + 1);

    /* num_decided個目の要素を"選ぶ"場合のパターンを作成 */
    pattern[num_decided] = 1;
    combination(pattern, elems, n, r, num_decided + 1);
}

再帰呼び出しで組み合わせを全列挙する関数（重複なし） で紹介した関数 combination に比べて下記部分を追加しています。

if (num_selected > r) {
    /* 既にrを超えて選んでいる場合 */
    return;
}

if (r - num_selected > n - num_decided) {
    /* r個選ぶのに要素の数が足りない場合 */
    return;
}

再帰呼び出しの場合、一手戻す処理は再帰呼び出しを行うことなく return を実行することになります。

上記では、組み合わせのパターンとして条件に合致し得ない、つまり選ぶ要素の数が r になり得ない場合に return を実行して一手戻す処理を行なっています。組み合わせのパターンとして条件に合致し得ないと分かった瞬間に、そのパターンを継続して作成することをやめて他のパターンを試すことになるので、その分処理効率を高めることが出来ます。

例えば、N = 28、R = 14 とした場合、再帰呼び出しで組み合わせを全列挙する関数（重複なし） で紹介した combination 関数が終了するのに約４０秒かかりましたが、上記のバックトラックを利用した combination 関数は約１８秒程度で終了しました（両方とも printCombination の実行をコメントアウトして時間を計測）。簡単な変更ですが、それなりに効果があることが確認していただけると思います。 

スポンサーリンク

組み合わせの全パターンを列挙する（重複あり）

続いては、重複ありで組み合わせの全パターンを列挙する方法について解説していきます。

重複ありで組み合わせの全パターンを列挙する考え方

重複ありの場合でも、基本的な考え方は重複無しの場合と同じで、n 個の要素から要素を選ぶときの全パターンのうち、「r 個のみ “選ぶ” になっている」という条件を満たしているパターンのみが、n 個の要素から r 個の要素を選んだ際の組み合わせのパターンとなります。

ですので、n 個の要素から要素を選ぶときの全パターンの中から、「r 個のみ “選ぶ” になっている」という条件を満たしているパターンのみを表示してやれば、n 個の要素から r 個の要素を選んだ際の組み合わせのパターンを全列挙することが出来ます。

ただし、重複なしの場合、１つの要素に対して行われる操作は下記の２つのどちらかでした。

• 選ぶ
• 選ばない

それに対し、重複ありの場合、同じ要素が複数回選ばれる可能性があり、１つの要素に対して行われる操作は下記の r + 1 個のいずれかとなります。

• 0 回選ぶ
• 1 回選ぶ
• 2 回選ぶ
• 〜略〜
• r - 1 回選ぶ
• r 回選ぶ

重複なしの場合は、配列 pattern を用意し、”選ぶ” or “選ばない” のそれぞれを示す 0 or 1 の値を格納することでパターンを作成していきましたが、重複ありの場合は、配列 pattern に選ばれた回数 0 〜 r の値を格納することでパターンを作成していくことになります。

そして、パターン作成後に配列 pattern の各要素の値を足し合わせた結果が r になっている場合のみパターンを表示してやれば、n 個の要素から r 個の要素を選んだ際の組み合わせのパターンを全列挙することが出来ます。

要は、重複なしとの大きな違いは配列 pattern に格納する値のみであり、重複なしで用意した関数を少し変更することで、重複ありの場合の組み合わせのパターンの全列挙を実現することができます。

ループで組み合わせを全列挙する関数（重複あり）

重複ありで、ループを用いて n = 5 個の要素から r 個の要素を選ぶ際の組み合わせの全パターンを列挙する関数は下記の combination 関数のようになります。

/* n個の要素からr個の要素を選ぶ場合の全パターンを列挙する */
void combination(int pattern[], char elems[], int n, int r) {

    for (int a = 0; a <= r; a++) {
        /* 第0個目の要素を選んだ回数を決定 */
        pattern[0] = a;
        for (int b = 0; b <= r; b++) {
            /* 第1個目の要素を選んだ回数を決定 */
            pattern[1] = b;
            for (int c = 0; c <= r; c++) {
                /* 第2個目の要素を選んだ回数を決定 */
                pattern[2] = c;
                for (int d = 0; d <= r; d++) {
                    /* 第3個目の要素を選んだ回数を決定 */
                    pattern[3] = d;
                    for (int e = 0; e <= r; e++) {
                        /* 第4個目の要素を選んだ回数を決定 */
                        pattern[4] = e;

                        /* "選ぶ"と決定された要素の数がrの場合のみパターンを表示 */
                        if (getNumSelected(pattern, n) == r) {
                            printCombination(pattern, elems, n);
                        }
                    }
                }
            }
        }
    }

}

ループで組み合わせを全列挙する関数（重複なし） で紹介した combination 関数との違いは、コメント部分を除けば a 〜 e に対するループの継続条件部分のみになります。

前述の通り、重複なしの場合は１つの要素に対して行われる操作は “選ぶ” or “選ばない” の 2 つのみでしたので、各ループの条件は a <= 1 のように 0 と 1 の値しか取らないように継続条件を設定していました。

それに対して重複ありの場合は、１つの要素に対して行われる操作は “0 回選ぶ” 〜 “r 回選ぶ” の r + 1 個となりますので、それに合わせて各ループの条件は a <= r のように 0 〜 r の値を取るように継続条件を変更しています。

これによって、pattern[i] に 0 〜 r の値が設定され、elems における第 i 個目の要素が 0 〜 r 回選ばれた時のパターンを作成することが出来ます。

他の部分は、ループで組み合わせを全列挙する関数（重複なし） で紹介した combination 関数と全く同じになります（コメントを除いて）。

スポンサーリンク

再帰呼び出しで組み合わせを全列挙する関数（重複あり）

重複ありで、再帰呼び出しを用いて n 個の要素から r 個の要素を選ぶ際の組み合わせの全パターンを列挙する関数は下記の combination 関数のようになります。

/* n個の要素からr個の要素を選ぶ場合の全パターンを列挙する */
void combination(int pattern[], char elems[], int n, int r, int num_decided) {

    int num_selected = getNumSelected(pattern, num_decided);

    if (num_decided == n) {
        /* n個全ての要素に対して"選ぶ"or"選ばない"が決定ずみ */
        if (num_selected == r) {
            /* r個だけ選ばれている場合のみ、選ばれた要素を表示 */
            printCombination(pattern, elems, n);
        }
        return;
    }

    for (int i = 0; i <= r; i++) {

        /* num_decided個目の要素をi回選んだ場合のパターンを作成 */
        pattern[num_decided] = i;
        combination(pattern, elems, n, r, num_decided + 1);
    }
}

再帰呼び出しで組み合わせを全列挙する関数（重複なし） で紹介した combination 関数では、pattern[num_decided] に 0 を格納してから combination 関数を再帰呼び出しを行い、さらに pattern[num_decided] に 1 を格納してから combination 関数を再帰呼び出しするように処理を行なっていました。

それに対し、重複ありの場合は、pattern[num_decided] に 0 〜 r を格納してから combination 関数を再帰呼び出しする必要があります。ですので、上記のように for ループを組み、その中で i を 0 〜 r まで変化させながら、pattern[num_decided] への i の格納と combination 関数の再帰呼び出しを繰り返し行うようにしています。

したがって、再帰呼び出しで組み合わせを全列挙する関数（重複なし） で紹介した combination 関数では下の図のように枝が 2 本ずつ分かれながら再帰呼び出しと pattern の生成が段階的に行われていくイメージでしたが、上記の combination 関数では r + 1 本ずつ枝分かれしながら再帰呼び出しと pattern の生成が段階的に行われていくイメージで処理が進むことになります。

バックトラックで組み合わせを全列挙する関数（重複あり）

重複ありの場合でも、バックトラックの考え方は適用できます。ただし、バックトラックで組み合わせを全列挙する関数（重複なし） では一手戻す処理を下記の２つの場合に行いましたが、

if (num_selected > r) {
    /* 既にrを超えて選んでいる場合 */
    return;
}

if (r - num_selected > n - num_decided) {
    /* r個選ぶのに要素の数が足りない場合 */
    return;
}

重複ありの場合は一手戻すのは下記の１つの場合のみとなります。

if (num_selected > r) {
    /* 既にrを超えて選んでいる場合 */
    return;
}

理由は簡単で、重複ありの場合は１つの要素を最大 r 回選ぶことができるため、パターンを作成している途中で選ぶ要素の個数が r に足りないと判断できる場合がないからです。

そのため、バックトラック法を用いた場合の、n 個の要素から r 個の要素を選ぶ際の組み合わせの全パターンを列挙する関数は下記の combination 関数のようになります。

/* n個の要素からr個の要素を選ぶ場合の全パターンを列挙する */
void combination(int pattern[], char elems[], int n, int r, int num_decided) {

    int num_selected = getNumSelected(pattern, num_decided);

    if (num_decided == n) {
        /* n個全ての要素に対して"選ぶ"or"選ばない"が決定ずみ */
        if (num_selected == r) {
            /* r個だけ選ばれている場合のみ、選ばれた要素を表示 */
            //printCombination(pattern, elems, n);
            count++;
        }
        return;
    }


    if (num_selected > r) {
        /* 既にrを超えて選んでいる場合 */
        return;
    }

    for (int i = 0; i <= r; i++) {

        /* num_decided個目の要素をi回選んだ場合のパターンを作成 */
        pattern[num_decided] = i;
        combination(pattern, elems, n, r, num_decided + 1);
    }
}

まとめ

このページでは、C言語で組み合わせの全パターンを列挙する方法について解説しました。

n 個の要素から r 個の要素を選んだ際の組み合わせのパターンを全列挙は、n 個の要素から要素を選ぶときの全パターンの中から、「r 個のみ “選ぶ” になっている」という条件を満たしているパターンのみを表示してやることで実現することが出来ます。

こういった全パターンを作成するようなやり方（全探索）は、再帰呼び出しを利用するとサクッと実装できたりすることが多いです。ただ、再帰呼び出しは、再帰呼び出しの深さが深くなるとスタックオーバーフローが発生することもあるので注意してください。

また、今回紹介した全探索はいろんな問題を解く際にも結構使えるテクニックですので是非覚えておいてください。ただ、データの個数が多い場合は処理速度が遅くなり、プログラムが終了しなくなる可能性もあります。

そういった場合に、他のアルゴリズムを適用することで処理速度を向上させることができることもあります。例えば下記ページで動的計画法の解説も行っていますので、そういったアルゴリズムを知りたい方は是非読んでみてください！

【C言語】動的計画法をナップサック問題を解いて理解する

オススメの参考書（PR）

C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです！

スッキリわかるC言語入門 第2版

posted with ヨメレバ

中山 清喬/株式会社フレアリンク インプレス 2021年12月14日頃

楽天ブックス

Amazon

Kindle

 

まず学習を進める上で、参考書は２冊持っておくことをオススメします。この理由は下記の２つです。

• 参考書によって、解説の仕方は異なる
• 読み手によって、理解しやすい解説の仕方は異なる

ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね！」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか？

それと同じで、１冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。

なので、参考書は２冊持っておいた方が学習時に挫折しにくいというのが私の考えです。

特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか？」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。

もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう！もちろん私のサイトも参考にしていただけると嬉しいです！

入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。

https://daeudaeu.com/c_reference_book/