例外付き組み合わせ
総当たりで解を出すプログラム。
NUM_ALLは母集団に含まれる要素の数。
数を変更する場合は、combine_tableをそれに見合う大きさに書き直す必要がある。
(combine_tableの対角線上とそれより左下の領域は使用しないので全て0でよい。)
NUM_SELECTは選び出す数。2以上を指定すること。
1の場合は母集団の要素の数に等しいので計算する必要はない。
combine_tableは使えない組み合わせのところを1にする。
#include <stdio.h>
#include <stdlib.h>#define NUM_ALL 8
#define NUM_SELECT 5const char combine_table[NUM_ALL][NUM_ALL]={
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}
};int main(void){
int depth, i, j;
char table[NUM_ALL][NUM_SELECT], choice[NUM_SELECT];
int num;
int to_next;choice[0]=0;
choice[1]=1;
depth=0;
num=0;while(choice[0] <= NUM_ALL - NUM_SELECT + 1){
if (depth!=0)
for(i=choice[depth]+1; i< NUM_ALL; i++)
table[i][depth] = combine_table[choice[depth] ][i] + table[i][depth-1];
else
for(i=choice[depth]+1; i< NUM_ALL; i++)
table[i][depth] = combine_table[choice[depth] ][i];
to_next=1;for(i=choice[depth+1]; i <= (NUM_ALL - NUM_SELECT + depth + 1); i++){
printf("Check");
for(j=0; j<=depth ; j++){
printf(" %d", choice[j]);
}
printf(" %d\n", i);if(table[i][depth]==0){
if(depth == NUM_SELECT -1 -1){
printf("Choices are");
choice[depth+1]=i;
for(j=0; j<NUM_SELECT; j++)
printf(" %d", choice[j]);
printf("\n");num +=1;
}
else{
depth++;
choice[depth]=i;
choice[depth+1]=i+1;
to_next=0;
break;
}
}
}if(to_next!=0){
choice[depth]+=1;
if(depth>0)
depth-=1;
else
choice[1]=choice[0]+1;
}
}printf("%d pattern(s).\n", num);
return 0;
}
0-7の8個の数字から5個の組み合わせを探した時(上記のソースのまま)の出力。
不可能な組み合わせは0-4, 1-5, 3-4, 3-6。
Check 0 1
Check 0 1 2
Check 0 1 2 3
Check 0 1 2 3 4
Check 0 1 2 3 5
Check 0 1 2 3 6
Check 0 1 2 3 7
Choices are 0 1 2 3 7
Check 0 1 2 4
Check 0 1 2 5
Check 0 1 2 6
Check 0 1 2 6 7
Choices are 0 1 2 6 7
Check 0 1 3
Check 0 1 3 4
Check 0 1 3 5
Check 0 1 3 6
Check 0 1 4
Check 0 1 5
Check 0 2
Check 0 2 3
Check 0 2 3 4
Check 0 2 3 5
Check 0 2 3 5 6
Check 0 2 3 5 7
Choices are 0 2 3 5 7
Check 0 2 3 6
Check 0 2 4
Check 0 2 5
Check 0 2 5 6
Check 0 2 5 6 7
Choices are 0 2 5 6 7
Check 0 3
Check 0 3 4
Check 0 3 5
Check 0 3 5 6
Check 0 4
Check 1 2
Check 1 2 3
Check 1 2 3 4
Check 1 2 3 5
Check 1 2 3 6
Check 1 2 4
Check 1 2 4 5
Check 1 2 4 6
Check 1 2 4 6 7
Choices are 1 2 4 6 7
Check 1 2 5
Check 1 3
Check 1 3 4
Check 1 3 5
Check 1 4
Check 1 4 5
Check 2 3
Check 2 3 4
Check 2 3 5
Check 2 3 5 6
Check 2 4
Check 2 4 5
Check 2 4 5 6
Check 2 4 5 6 7
Choices are 2 4 5 6 7
Check 3 4
6 pattern(s).
エンバグしていませんように。
