C言語で重複組み合わせの要素数の列挙関数

15370 ワード
関数 C C テキストリンク

問題

n 個から k 個を重複ありで取り出す組み合わせで、n 個の要素からそれぞれ何個ずつ取り出されたかを列挙したい。例えば、n=3、k=2の場合、列挙した要素数を単純に出力すると以下のようになる汎用関数を定義したい。

2,0,0,
1,1,0,
1,0,1,
0,2,0,
0,1,1,
0,0,2,

C言語で実装する場合、以下の3通りの方法が考えられる。

  1. (n-1)重ループを書く
  2. 再帰
  3. 先頭の組み合わせを返す関数、組み合わせを受け取って次の組み合わせを返す関数を用意

(n-1)重ループを書く

こちらの方法は、n が固定の場合しか使えないので、n が変わるたび・内部処理が変わるたびに毎回同じようなコードを手動で書かなければならないという問題がある。

#include <stdio.h>

int main() {
    long long rest = 2;
    for (long long p0 = rest; p0 >= 0; --p0) {
        rest -= p0;
        for (long long p1 = rest; p1 >= 0; --p1) {
            rest -= p1;
            /* ここに列挙した要素数を処理するコードを追加 */
            printf("%lld,%lld,%lld,\n", p0, p1, rest);
            /* ここまで */
            rest += p1;
        }
        rest += p0;
    }
}

再帰

こちらの方法も、内部処理が変わるたびに毎回同じようなコードを手動で書かなければならないという問題がある。(関数ポインタとvoidポインタを渡すインターフェースにすれば汎用的に使える関数になるが、使うためにいちいち関数と構造体定義が必要で面倒。クロージャが使える言語なら、この選択肢もあり)

#include <stdio.h>
#include <stddef.h>

void multicombination_count_rec(ptrdiff_t i, ptrdiff_t n, long long rest, long long* pattern) {
    if (i >= n - 1) {
        if (n > 0)
            pattern[n - 1] = rest;
        /* ここに列挙した要素数を処理するコードを追加 */
        for (ptrdiff_t j = 0; j < n; ++j)
            printf("%lld,", pattern[j]);
        printf("\n");
        /* ここまで */
    }
    else {
        for (long long p = rest; p >= 0; --p) {
            pattern[i] = p;
            multicombination_count_rec(i + 1, n, rest - p, pattern);
        }
    }
}

void multicombination_count(ptrdiff_t n, long long k, long long* pattern) {
    if (!(n < 0 || k < 0 || (n == 0 && k > 0)))
        multicombination_count_rec(0, n, k, pattern);
}

/* 使用例 nが0以下の場合はpatternの定義を削除してNULLを渡すこと */
int main() {
    long long pattern[3];
    multicombination_count(3, 2, pattern);
}

先頭の組み合わせを返す関数、組み合わせを受け取って次の組み合わせを返す関数を用意

こちらの方法は、内部処理が変わっても関数自体の書き換えが不要なので、ライブラリとして汎用的に使える形にすることができる。以下の使用例のようにif～do～whileでループのように使える。

#include <stdio.h>
#include <stddef.h>

int init_multicombination_count(ptrdiff_t n, long long k, long long* pattern) {
    if (n <= 0 || k < 0)
        return n == 0 && k == 0;
    pattern[0] = k;
    for (ptrdiff_t i = 1; i < n; ++i)
        pattern[i] = 0;
    return 1;
}

int next_multicombination_count(ptrdiff_t n, long long* pattern) {
    ptrdiff_t i = n - 2;
    for (; i >= 0 && pattern[i] == 0; --i)
        ;
    if (i < 0)
        return 0;
    --pattern[i];
    pattern[i + 1] = pattern[n - 1] + 1;
    if (i + 1 != n - 1)
        pattern[n - 1] = 0;
    return 1;
}

/* 使用例 nが0以下の場合はpatternの定義を削除してNULLを渡すこと */
int main() {
    long long pattern[3];
    if (init_multicombination_count(3, 2, pattern))
        do {
            /* ここに列挙した要素数を処理するコードを追加 */
            for (size_t i = 0; i < 3; ++i)
                printf("%lld,", pattern[i]);
            printf("\n");
            /* ここまで */
        } while (next_multicombination_count(3, pattern));
}

注意

こちらのコードは、n,kを指定して列挙、もしくは列挙結果をもとにした計算を行うという関数の提示を目的としています(最初の方法を除く)。関数については汎用で使えるよう配慮していますが、呼び出し側のmain関数はあくまで使用例の1つとして提示しているだけなので、実際の用途に応じて書き換えてください。

提示した関数の最後の引数については、呼び出し側でサイズ n のlong long型のメモリを確保して呼び出してください。ただし、n<=0の場合は何を渡しても構いません。

n,k に異常値を渡した場合は、表示用のfor文は一度も実行されません。具体的には、n<0の場合、k<0の場合、n==0 && k>0の場合が異常値として扱われます。なお、n==0 && k==0の場合は正常値として扱われ、空の配列に対して表示用のfor文が1度だけ呼び出されます。