C言語で組み合わせを計算する方法

C言語では、再帰関数を使用して組み合わせを実現できます。

よく使われる方法として、すでに選択した要素を保存する配列を定義し、再帰関数を使用して順列と組み合わせを生成する方法がある。

再帰関数を使用して順列と組み合わせを実装するサンプルコードを以下に示します。

#include <stdio.h>

void combination(int n, int m, int index, int* selected, int selectedCount) {
    if (selectedCount == m) {
        for (int i = 0; i < m; i++) {
            printf("%d ", selected[i]);
        }
        printf("\n");
        return;
    }

    if (index >= n) {
        return;
    }

    selected[selectedCount] = index + 1;
    combination(n, m, index + 1, selected, selectedCount + 1);

    combination(n, m, index + 1, selected, selectedCount);
}

int main() {
    int n = 5;  // 总共的元素个数
    int m = 3;  // 需要选择的元素个数
    int selected[m];  // 保存已经选择的元素

    combination(n, m, 0, selected, 0);

    return 0;
}

上記のコード内のcombination関数は順列組み合わせを生成するためのものであり、nが要素の総数、mが選択する要素の数、indexが現在処理している要素のインデックス、selectedが選択された要素の配列、selectedCountが選択された要素の数です。

再帰関数で順列組み合わせを生成する場合、終了条件は2つあります。選んだ要素の数が要求通りの数と同じ場合は、結果を出力して戻る。現在の処理中の要素の添字が要素の総数以上の場合は戻る。それ以外は、現在の要素を選択した要素の配列に加えて、再帰的に次の要素を処理し、その後現在の要素を選択した要素の配列から削除して、再帰的に次の要素を処理する。

上記コードを実行すると、すべての 3 つの要素の順列が生成されます。