C言語による組み合わせのアルゴリズム

2年 ago
海斗, 葵
1 minute

C言語の組み合わせアルゴリズムは再帰で実現可能です。以下はそのサンプルコードです:

#include <stdio.h>

void combination(int arr[], int data[], int start, int end, int index, int r) {
    if (index == r) {
        for (int i = 0; i < r; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
        return;
    }
    
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        data[index] = arr[i];
        combination(arr, data, i + 1, end, index + 1, r);
    }
}

void permutation(int arr[], int data[], int start, int end) {
    if (start == end) {
        for (int i = 0; i <= end; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
        return;
    }
    
    for (int i = start; i <= end; i++) {
        int temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
        
        permutation(arr, data, start + 1, end);
        
        temp = arr[start];
        arr[start] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int r = 2;
    int data[r];
    
    printf("Combination:\n");
    combination(arr, data, 0, n - 1, 0, r);
    
    printf("Permutation:\n");
    permutation(arr, data, 0, n - 1);
    
    return 0;
}

上記のコード内では、combination関数はコンビネーションの計算を行い、permutation関数はパーミテーションの計算を行います。arr配列は元のデータを格納し、data配列は現在のコンビネーションまたはパーミテーションの結果を格納します。startとendパラメータは現在処理すべき配列の範囲を指定し、indexパラメータは現在何個の数が選択されているかを指定します。rパラメータはコンビネーションまたはパーミテーションのために選択する必要がある数の数を指定します。

combination関数では、バックトラック法を用いて再帰的に組み合わせアルゴリズムを実現する。各再帰段階で、startからendの範囲内で数を1つ選び、data配列に格納した後、combination関数を再帰呼び出しし、次の数を選択し続け、r個の数を選択するまで続ける。

再帰呼び出しによる巡回法を用いて、permutation関数で順序付けアルゴリズムを実現しています。それぞれの再帰階層で、arr[start]とarr[i]の位置を入れ替え、順序付けが完了するまで再帰呼び出しを続けて、次の位置へ移動しています。

メイン関数では、サンプル配列arrと選択数rを定義し、combination関数とpermutation関数を実行して、その結果を出力します。

bannerAds