C言語 数列の要素を選ぶ組み合わせをビット列で表現するコード

各要素について選択するかしないかの2択となるので、2^n 通りの組み合わせがあります。これらは次の再帰によるアルゴリズムで生成することができます。

S を S[i] が 1 のとき i 番目の整数を選択する、0 のとき選択しない、という配列とします。

#include <stdio.h>
#define N 3

int S[N];

void makeCombination(int i);
void print_array(int array[], int array_len);

void makeCombination(int i)
{
    if (i == N)
    {
        print_array(S, N);
        return;
    }
    makeCombination(i + 1);
    S[i] = 1;
    makeCombination(i + 1);
    S[i] = 0;
}

void print_array(int array[], int array_len)
{
    printf("S {");
    for (int i = 0; i < array_len; i++)
    {
        printf("%d", array[i]);
        if (i != array_len - 1)
            printf(", ");
    }
    printf("}\n");
}

int main(void)
{
    makeCombination(0);
    return 0;
}

N=3のときの出力結果

S {0, 0, 0}
S {0, 0, 1}
S {0, 1, 0}
S {0, 1, 1}
S {1, 0, 0}
S {1, 0, 1}
S {1, 1, 0}
S {1, 1, 1}

参考

感想

相変わらず再帰は直感的に理解しにくい