組み合わせ全パターン取得

[早苗明紗]

いつもお世話になっております。

今回もお力添えをいただきたくトピックを立てさせていただきました。

組み合わせ nCr の n が与えられたら r を含めたすべてのパターンを取得するプログラムを作りたいと考えています。
例として、 4 が与えられたら
{ 0 } , { 1 }, { 2 }, { 3 }
{ 0,1 }, { 0,2 }, { 0,3 }, { 1,2 }, { 1,3 }, { 2,3 }
{ 0,1,2 }, { 0,1,3 }, { 0,2,3 }, { 1,2,3 }
{ 1,2,3,4 }
の15パターンを取得することになります。

コードがまったく思いつかず、お手上げ状態です。

コード:

int Comb; //nCrの値
for( int i=0 ; i<n ; i++ )
{
    Comb = 1;
    // nCrの値を求める
    for( int j=0 ; j<i+1 ; j++ )
    {
        Comb = Comb * (n-j)/(j+1)
    }
    for( int j=0 ; j<Comb ; j++ )
    {
        //ここに組み合わせパターンを取得するプログラムを入れる
    }
}

ヒントをいただけないでしょうか

[h2so5]

4bitの整数の各ビットをそれぞれ 0, 1, 2, 3に割り当てれば、 1 〜 15 で全パターン出力できます。

1 - 0001 - { 0 }
2 - 0010 - { 1 }
3 - 0011 - { 0, 1 }
4 - 0100 - { 2 }
5 - 0101 - { 0, 2 }
...

[早苗明紗]

そんな手があったのですね。
ただ、nが３や５の場合、3bitや5bitの整数を用意するのは難しいので、
1~2^n-1までの整数を2進数で表すためのプログラムにすればよいのかもしれません。

ありがとうございました。

[みけCAT]

ただ、nが３や５の場合、3bitや5bitの整数を用意するのは難しいので、
1~2^n-1までの整数を2進数で表すためのプログラムにすればよいのかもしれません。

PCでの「一般的」なC言語には4bitの整数型もありませんが…(ビットフィールドを使えば表現できるかもしれませんが)

コード:

#include <stdio.h>

int main(void) {
	int n;
	int i,imax;
	if(scanf("%d",&n)!=1 || n>30 || n<1) {
		puts("bad input");
		return 1;
	}
	for(i=1,imax=1<<n;i<imax;i++) {
		int is_first=1;
		int j;
		printf("{ ");
		for(j=0;j<n;j++) {
			if((i>>j)&1) {
				if(!is_first)printf(",");
#if 0
				/* 直感的な出力 */
				printf("%d",j);
#else
				/* サンプルに合わせた出力 */
				printf("%d",j+(i+1<imax?0:1));
#endif
				is_first=0;
			}
		}
		printf(" }\n");
	}
	return 0;
}

[かずま]

みけCATさんのプログラムの実行結果

コード:

4
{ 0 }
{ 1 }
{ 0,1 }
{ 2 }
{ 0,2 }
{ 1,2 }
{ 0,1,2 }
{ 3 }
{ 0,3 }
{ 1,3 }
{ 0,1,3 }
{ 2,3 }
{ 0,2,3 }
{ 1,2,3 }
{ 1,2,3,4 }

なんかおかしいので、私も書いてみました。

コード:

#include <stdio.h>

void comb(int n)
{
    int i, j, k, m = 1 << n;
    for (i = 1; i < m; i++) {
        for (j = k = 0; j < n; j++)
            if (i>>j & 1)
                k = printf("%c %d", ",{"[!k], j+1);
        printf(" }\n");
    }
}

int main(void)
{
    int n;
    while (printf(">> "), scanf("%d", &n) == 1 && n > 0 && n < 30)
        comb(n);
    return 0;
}

実行結果

コード:

>> 4
{ 1 }
{ 2 }
{ 1, 2 }
{ 3 }
{ 1, 3 }
{ 2, 3 }
{ 1, 2, 3 }
{ 4 }
{ 1, 4 }
{ 2, 4 }
{ 1, 2, 4 }
{ 3, 4 }
{ 1, 3, 4 }
{ 2, 3, 4 }
{ 1, 2, 3, 4 }
>> .

順番がいまいちなので、書き直し。

コード:

#include <stdio.h>

int n, r, u[32];

void comb(int k, int m)
{
    int i;
    if (k)
        for (i = m; i <= n - k + 1; i++)
            u[k] = i, comb(k-1, i+1);
    else
        for (i = r; i > 0; i--)
            printf("%c %d%s", "{,"[i!=r], u[i], i==1?" }\n":"");
}

int main(void)
{
    while (printf(">> "), scanf("%d", &n) == 1 && n > 0 && n < 30)
        for (r = 1; r <= n; r++) comb(r, 1);
    return 0;
}

実行結果

コード:

>> 4
{ 1 }
{ 2 }
{ 3 }
{ 4 }
{ 1, 2 }
{ 1, 3 }
{ 1, 4 }
{ 2, 3 }
{ 2, 4 }
{ 3, 4 }
{ 1, 2, 3 }
{ 1, 2, 4 }
{ 1, 3, 4 }
{ 2, 3, 4 }
{ 1, 2, 3, 4 }
>> .

[みけCAT]

みけCATさんのプログラムの実行結果

コード:

4
{ 0 }
{ 1 }
{ 0,1 }
{ 2 }
{ 0,2 }
{ 1,2 }
{ 0,1,2 }
{ 3 }
{ 0,3 }
{ 1,3 }
{ 0,1,3 }
{ 2,3 }
{ 0,2,3 }
{ 1,2,3 }
{ 1,2,3,4 }

なんかおかしいので、私も書いてみました。

きちんと順番を除いてサンプルに一致しているのに、どこがおかしいと感じたのですか？
かずまさんのプログラムの出力はサンプルすら一致していないので、私としてはそっちの方がおかしいと思います。

きちんと順番も合わせたプログラムを書いてみました。

コード:

#include <stdio.h>
#include <stdlib.h>

void dfs(int arr[], int pos, int take_num, int n, int next, int is_first) {
	if (pos >= take_num) {
		/* 1個の組み合わせが最後まで求まった */
		int i;
		if (is_first == 0) printf(", ");
		/* 組み合わせを出力する */
		printf("{ ");
		for (i = 0; i < take_num; i++) {
			if (i > 0) putchar(',');
			if (take_num == n) {
				printf("%d", arr[i] + 1);
			} else {
				printf("%d", arr[i]);
			}
		}
		printf(" }");
		if (take_num == 1 && n > 1 && is_first) putchar(' ');
	} else {
		int i;
		/* 組み合わせを作る数字が足りないので、枝刈りを行う */
		if (n - next + 1 < take_num - pos) return;
		/* 次の数字を探索する */
		for (i = next; i < n; i++) {
			arr[pos] = i;
			dfs(arr, pos + 1, take_num, n, i + 1, is_first);
			is_first = 0;
		}
	}
}

int main(void) {
	int n;
	int i;
	int *arr;
	/* 入力 */
	if (scanf("%d", &n) != 1 || n <= 0) {
		puts("bad input");
		return 1;
	}
	/* メモリ確保 */
	arr = (int *) malloc(sizeof(int) * n);
	if (arr == NULL) {
		puts("memory allocate error");
		return 1;
	}
	/* 各rごとに組み合わせを取得する */
	for (i = 1; i <= n; i++) {
		dfs(arr, 0, i, n, 0, 1);
		putchar('\n');
	}
	free(arr);
	return 0;
}

実行結果

コード:

{ 0 } , { 1 }, { 2 }, { 3 }
{ 0,1 }, { 0,2 }, { 0,3 }, { 1,2 }, { 1,3 }, { 2,3 }
{ 0,1,2 }, { 0,1,3 }, { 0,2,3 }, { 1,2,3 }
{ 1,2,3,4 }

https://ideone.com/uAXjP5

オフトピック

といっても、n=4以外のときにどのような出力をするのが正解なのかは今のところわかりませんが…

[かずま]

きちんと順番を除いてサンプルに一致しているのに、どこがおかしいと感じたのですか？
かずまさんのプログラムの出力はサンプルすら一致していないので、私としてはそっちの方がおかしいと思います。

サンプルというのは、質問者の挙げたものですね。
申し訳ありません。私は、それを全く見落としていました。

「組み合わせ nCr の n が与えられたら r を含めたすべての
パターンを取得するプログラム」 という部分だけに反応して、
n が 4 なら、1～4 の ４個の数を並べるものだと思ってしまいました。

そして、みけCATさんのプログラムを走らせてみると、
0～4 の 5個の数字が出てくるので 「おかしい」 と書いてしまいました。

n が 4 なら、0～3 または 1～4 の 4個の数を並べるはずなので、
元の質問者の挙げたサンプルがそもそもおかしかったのですね。

みけCATさんのプログラムは、それを忠実に再現するもので
感服しますが、サンプルがおかしいとは思わなかったのでしょうか？

[みけCAT]

みけCATさんのプログラムは、それを忠実に再現するもので
感服しますが、サンプルがおかしいとは思わなかったのでしょうか？

たしかに不自然で、(n=4以外の入力に対して)well-definedでないと思いましたが、致命的な矛盾はなく、

例として、 4 が与えられたら
{ 0 } , { 1 }, { 2 }, { 3 }
{ 0,1 }, { 0,2 }, { 0,3 }, { 1,2 }, { 1,3 }, { 2,3 }
{ 0,1,2 }, { 0,1,3 }, { 0,2,3 }, { 1,2,3 }
{ 1,2,3,4 }
の15パターンを取得することになります。

というように言い切っているので、これが今回の問題の「仕様」であり、プログラムは「仕様」に合わせるべきだと思いました。