組合せ生成プログラム

/*		comb.c		組合せ(nＣk)の生成	generation of combination		*/
#include <stdio.h>
#include <math.h>

#define		set			unsigned int

set K, N, x, overx;

extern void showcomb(int p[], int n, int k);	/* このルーチンで各組合せに対する処理を行う */
void gencomb(int p[], int n, int k);	/* 組合せ生成マスタールーチン */
void gencomb1(int p[], int n, int k);	/* 高速組合せ生成ルーチン（但し、n < 16）	*/
void gencomb2(int p[], int n, int k);	/* 組合せ生成ルーチン（n > 15 で使用）	*/
int subcomb(int p[]);	/* gencomb1() のスレーブルーチン */
set nextset(void);		/* gencomb1() のスレーブルーチン */

void gencomb(int p[], int n, int k)
{
	int i;

	if(n < k || k <= 0)
	{
		fprintf(stderr, "Error : illegal parameter input  in gencomb().\n");
		return;
	}
	if(k == 0)
	{
		p[0] = -1;
		fprintf(stderr, "Warning : nＣk (k=0).  No combination select.\n");
		return;
	}
	if(n < 16)	gencomb1(p, n, k);
	else		gencomb2(p, n, k);
	return;
}

void gencomb1(int p[], int n, int k)
{
	int j, *q;
	set s;

	N = n;
	K = k;
	x = (1 << K) - 1L;
	overx = ~((1 << N) - 1L);
	for(j = 1, q = p, s = x; j <= N; j++)
	{
		if(s & 1)	*q++ = j;
		s >>= 1;
	}
	while(subcomb(p))	showcomb(p, n, k);
}

int subcomb(int p[])
{
	int j, *q;
	set s;

	x = nextset();
	if(x & overx)	return 0;
	for(j = 1, q = p, s = x; j <= N; j++)
	{
		if(s & 1)	*q++ = j;
		s >>= 1;
	}
	return 1;
}

set nextset(void)
{
	set smallest, ripple, new_smallest, ones;

	smallest = x & -x;
	ripple = x + smallest;
	new_smallest = ripple & -ripple;
	ones = ((new_smallest / smallest) >> 1) - 1;
	return ripple | ones;
}

void gencomb2(int p[], int n, int k)
{
	int flag, i, j, nk;

	for(i = 0; i < k; i++)	p[i] = i;
	do
	{
		showcomb(p, n, k);
		flag = 0;
		for(i = k - 1, nk = n - 1; i >= 0; i--, nk--)
		{
			if(p[i] < nk)
			{
				flag = 1;
				p[i]++;
				for(j = i + 1; j < k; j++)	p[j] = p[j - 1] + 1;
				break;
			}
		}
	} while(flag);
}