C言語関係掲示板

過去ログ

No.999 「異なるn個の物からr個とる組合せ」のプログラム

[戻る] [ホームページ]
No.828

コンビネーション
投稿者---ゆうこ(初心者)(2003/12/15 00:40:31)


初めて投稿します。今、学校の自由課題で「異なるnこの物からr個とる組合せ」のプログラムを考えています。条件は、「再帰」を用いることで、入力はnとr、出力は、すべての組合せを辞書式に表示させることです。(例)n=3,r=2の時は、(1 2)(1 3)(2 3)となります。私は、コンビネーションを表す関数(comb)を再帰的に定義しようと考えています。また、r個の組合せを表すために、配列を使おうとしています。ここで質問ですが、combの引数は、n、r、A(配列)とあと何があれば、うまくプログラムを組み立てることができるでしょうか。プログラム例やアドバイスなどご教示願います。

No.829

Re:コンビネーション
投稿者---YuO(2003/12/15 02:27:56)


>私は、コンビネーションを表す関数(comb)を再帰的に定義しようと考えています。
>また、r個の組合せを表すために、配列を使おうとしています。
>ここで質問ですが、combの引数は、n、r、A(配列)とあと何があれば、うまくプログラムを組み立てることができるでしょうか。

私は,
static void combinationImpl (int r0, int r, int min, int max, int a[]);
void combination (int n, int r);

のように関数を作りました。

combination自体は外部から利用するための物なので,nとrを渡せば十分。
実際に再帰を利用して組み合わせを表示するのはcombinationImplの役割です。

例えば,combination(4, 3);は,
combinationImpl(3, 3, 1, 4, a);       /* a[1] = ?, a[2] = ?, a[3] = ? */
  combinationImpl(3, 2, 2, 4, a);     /* a[1] = ?, a[2] = ?, a[3] = 1 */
    combinationImpl(3, 1, 3, 4, a);   /* a[1] = ?, a[2] = 2, a[3] = 1 */
      combinationImpl(3, 0, 4, 4, a); /* a[1] = 3, a[2] = 2, a[3] = 1 → (1, 2, 3)と出力 */
      combinationImpl(3, 0, 5, 4, a); /* a[1] = 4, a[2] = 2, a[3] = 1 → (1, 2, 4)と出力 */
    combinationImpl(3, 1, 4, 4, a);   /* a[1] = ?, a[2] = 3, a[3] = 1 */
      combinationImpl(3, 0, 5, 4, a); /* a[1] = 4, a[2] = 3, a[3] = 1 → (1, 3, 4)と出力 */
  combinationImpl(3, 2, 3, 4, a);     /* a[1] = ?, a[2] = ?, a[3] = 2 */
    combinationImpl(3, 1, 4, 4, a);   /* a[1] = ?, a[2] = 3, a[3] = 2 */
      combinationImpl(3, 0, 5, 4, a); /* a[1] = 4, a[2] = 3, a[3] = 2 → (2, 3, 4)と出力 */

という再帰呼び出しを行います。
#配列変数を後ろ個から使うことやr = 0での呼び出しは手抜きの結果

結局,最初のrの値,値として使える範囲を引き渡す必要があります。
そして,nは値として使える範囲で指定できるので引き渡す必要が無くなります。


No.831

Re:コンビネーション
投稿者---かずま(2003/12/15 15:43:12)


> ここで質問ですが、combの引数は、n、r、A(配列)とあと何があれば、
> うまくプログラムを組み立てることができるでしょうか。

n も r も A も不変ですから、グローバル変数にしてもかまわないでしょう。
再帰を終了するための引数が必要です。それもグローバル変数にしようと思えば
できますが、そうしないほうが簡単に書けます。
#include <stdio.h>

int a[100], n, r;

void comb(int i)
{
    if (i <= r)
        for (a[i] = a[i-1] + 1; a[i] <= n; a[i]++) comb(i + 1);
    else {
        for (i = 1; i <= r; i++) printf(" %d", a[i]);
        printf("\n");
    }
}

int main(void)
{
    while (printf("n r ? "), scanf("%d%d", &n, &r) == 2) comb(1);
    return 0;
}
このプログラムは、無駄なところがあります。たとえば、n=5, r=3 の
とき、a[1] が 4 や 5 になることはないのに、それも試しています。
どうすればよいか考えてみてください。

comb を汎用的なものするなら、n, r, a を引数にしたり、構造体にして
ポインタを渡すというやり方もあるでしょう。C++ ならクラスを使う。

No.832

Re:コンビネーション
投稿者---ゆうこ(初心者)(2003/12/15 21:34:58)


YuOさん、かずまさん早速のプログラム例、アドバイスありがとうございました。勉強不足のためわからない言葉がいろいろありますので、まずは、ご教示頂いたプログラム、アドバイスをもとに自分で勉強したいと思います。本当にありがとうございました。

No.867

Re:コンビネーション
投稿者---かずま(2003/12/19 14:19:38)


> n も r も A も不変ですから、グローバル変数にしてもかまわないでしょう。
> 再帰を終了するための引数が必要です。それもグローバル変数にしようと思えば
> できますが、そうしないほうが簡単に書けます。

グローバル変数を使わず、再帰も使わないプログラムも示しておきましょう。
#include <stdio.h>

void comb(int n, int r)
{
    int a[100], i = 1, j;

    for (a[0] = 0; ; i++)
        for (a[i] = a[i-1] + 1; ; a[i]++) {
            if (i == r) {
                for (j = 1; j <= r; j++) printf(" %d", a[j]);
                printf("\n");
            }
            if (a[i] < n) break;
            if (--i == 0) return;
        }
}

int main(void)
{
    int n, r;

    while (printf("n r ? "), scanf("%d%d", &n, &r) == 2) comb(n, r);
    return 0;
}


No.903

Re:コンビネーション
投稿者---ゆうこ(初心者)(2003/12/23 22:13:57)


かずま様
さらなるご教授ありがとうございます。お返事遅れて申し訳ありません。ご教授いただいたプログラムをもとに、私が考えていた方針でなんとかプログラムは完成しました。ありがとうございました。