k-combinations iterator whose pairwise intersections contain no more than two elements

dualcomb.c

#include <stdio.h>

#define countof(x) (sizeof(x) / sizeof(*x))
#define MAX	(70U)
#define K	(8U)

static unsigned char comb[MAX][MAX];

/* 8-combinations */
static long unsigned int ncr[8U][70U] = {
	{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69},
	{0,0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346},
	{0,0,0,1,4,10,20,35,56,84,120,165,220,286,364,455,560,680,816,969,1140,1330,1540,1771,2024,2300,2600,2925,3276,3654,4060,4495,4960,5456,5984,6545,7140,7770,8436,9139,9880,10660,11480,12341,13244,14190,15180,16215,17296,18424,19600,20825,22100,23426,24804,26235,27720,29260,30856,32509,34220,35990,37820,39711,41664,43680,45760,47905,50116,52394},
	{0,0,0,0,1,5,15,35,70,126,210,330,495,715,1001,1365,1820,2380,3060,3876,4845,5985,7315,8855,10626,12650,14950,17550,20475,23751,27405,31465,35960,40920,46376,52360,58905,66045,73815,82251,91390,101270,111930,123410,135751,148995,163185,178365,194580,211876,230300,249900,270725,292825,316251,341055,367290,395010,424270,455126,487635,521855,557845,595665,635376,677040,720720,766480,814385,864501},
	{0,0,0,0,0,1,6,21,56,126,252,462,792,1287,2002,3003,4368,6188,8568,11628,15504,20349,26334,33649,42504,53130,65780,80730,98280,118755,142506,169911,201376,237336,278256,324632,376992,435897,501942,575757,658008,749398,850668,962598,1086008,1221759,1370754,1533939,1712304,1906884,2118760,2349060,2598960,2869685,3162510,3478761,3819816,4187106,4582116,5006386,5461512,5949147,6471002,7028847,7624512,8259888,8936928,9657648,10424128,11238513},
	{0,0,0,0,0,0,1,7,28,84,210,462,924,1716,3003,5005,8008,12376,18564,27132,38760,54264,74613,100947,134596,177100,230230,296010,376740,475020,593775,736281,906192,1107568,1344904,1623160,1947792,2324784,2760681,3262623,3838380,4496388,5245786,6096454,7059052,8145060,9366819,10737573,12271512,13983816,15890700,18009460,20358520,22957480,25827165,28989675,32468436,36288252,40475358,45057474,50063860,55525372,61474519,67945521,74974368,82598880,90858768,99795696,109453344,119877472},
	{0,0,0,0,0,0,0,1,8,36,120,330,792,1716,3432,6435,11440,19448,31824,50388,77520,116280,170544,245157,346104,480700,657800,888030,1184040,1560780,2035800,2629575,3365856,4272048,5379616,6724520,8347680,10295472,12620256,15380937,18643560,22481940,26978328,32224114,38320568,45379620,53524680,62891499,73629072,85900584,99884400,115775100,133784560,154143080,177100560,202927725,231917400,264385836,300674088,341149446,386206920,436270780,491796152,553270671,621216192,696190560,778789440,869648208,969443904,1078897248},
	{0ULL,0ULL,0ULL,0ULL,0ULL,0ULL,0ULL,0ULL,1ULL,9ULL,45ULL,165ULL,495ULL,1287ULL,3003ULL,6435ULL,12870ULL,24310ULL,43758ULL,75582ULL,125970ULL,203490ULL,319770ULL,490314ULL,735471ULL,1081575ULL,1562275ULL,2220075ULL,3108105ULL,4292145ULL,5852925ULL,7888725ULL,10518300ULL,13884156ULL,18156204ULL,23535820ULL,30260340ULL,38608020ULL,48903492ULL,61523748ULL,76904685ULL,95548245ULL,118030185ULL,145008513ULL,177232627ULL,215553195ULL,260932815ULL,314457495ULL,377348994ULL,450978066ULL,536878650ULL,636763050ULL,752538150ULL,886322710ULL,1040465790ULL,1217566350ULL,1420494075ULL,1652411475ULL,1916797311ULL,2217471399ULL,2558620845ULL,2944827765ULL,3381098545ULL,3872894697ULL,4426165368ULL,5047381560ULL,5743572120ULL,6522361560ULL,7392009768ULL,8361453672ULL},
};


static int
unrank(unsigned char x[static 1U], long unsigned int m)
{
	for (size_t k = K; k-- > 0U;) {
		size_t i;
		for (i = 1U; i < MAX && ncr[k][i] < m; i++);
		x[k] = --i;
		m -= ncr[k][i];
	}
	return 0;
}

static int
check(unsigned char x[static 1U], size_t nx)
{
	unsigned int viol = 0U;
	for (size_t i = 0U; i < nx; i++) {
		for (size_t j = i + 1U; j < nx; j++) {
			viol += comb[x[i]][x[j]];
			if (viol > 1U) {
				return -1;
			}
		}
	}
	return 0;
}

static int
marks(unsigned char x[static 1U], size_t nx)
{
	for (size_t i = 0U; i < nx; i++) {
		for (size_t j = i + 1U; j < nx; j++) {
			comb[x[i]][x[j]]++;
			comb[x[j]][x[i]]++;
		}
	}
	return 0;
}

static int
print(unsigned char x[static 1U], size_t nx)
{
	for (size_t i = 0U; i < nx; i++) {
		printf(" % 2hhd", x[i]);
	}
	puts("");
	return 0;
}

int
main(void)
{
	unsigned char curr[K];
	for (size_t i = 1ULL; i < 10000000000ULL; i++) {
		unrank(curr, i);
		if (check(curr, countof(curr)) >= 0) {
			marks(curr, countof(curr));
			print(curr, countof(curr));
		}
	}
	return 0;
}