プログラマ専用SNS ミクプラ

いつもお世話になっています。
今、グループスタイナーという問題のアルゴリズムを実装していまして、グラフの隣接行列に基づいた線形計画法の制約式を作成するC言語のプログラムを考えているのですが、行き詰ってしまいました。

まず、頂点数Cのグラフの隣接行列を与えます。
#define C 6
int c[C+1][C+1]={{0,0,0,0,0,0,0},
{0,0,1,M,1,M,1},
{0,1,0,1,M,1,M},
{0,M,1,0,1,M,1},
{0,1,M,1,0,1,0},
{0,M,1,M,1,0,1},
{0,1,M,1,M,1,0}};
例えば、c[1][3]が1というのは、頂点①と頂点③が繋がっている、という意味で、0とMは繋がっていない、
という意味です。

加えて、頂点の分割の情報
V0={1,2}
V1={3,4}
V2={5,6}
を与えます。これは頂点を①②のグループと③④のグループと⑤⑥のグループに分けるという意味です。
またこのグループに依存した変数
H(V0)=4
H(V1)=3
H(V2)=2
を与えます。

このとき、H(Vk)が一番大きいグループに属する頂点r(この場合では①と②)に関して、それぞれ制約式を作ります。

制約式は、一般化すると、
Σ{(Vkに属する頂点以外+頂点r)の頂点集合に"出入り"する辺}>=H(Vk)
(この場合、k=1or2※0は除く)と書けます。"(Vkに属する頂点以外+頂点r)の頂点集合"は様々なパターンがあるので、場合分けをしなければなりません。

具体的にはrが①の場合は、

(k=1)(①) x1_2+x1_4+x1_6>=3;
(①②) x1_6+x1_4+x2_5+x2_3>=3;
(①⑤) x1_2+x1_4+x1_6+x2_5+x4_5+x5_6>=3;
(①⑥) x1_2+x1_4+x3_6+x5_6>=3;
(①②⑤) x1_4+x1_6+x2_3+x4_5+x5_6>=3;
(①②⑥) x1_4+x2_3+x2_5+x3_6+x5_6>=3;
(①⑤⑥) x1_2+x1_4+x3_6+x2_5+x4_5>=3;
(①②⑤⑥)x1_4+x2_3+x3_6+x4_5>=3;
(k=2)(②) x1_2+x1_4+x1_6>=2;
(②①) x1_6+x1_4+x2_5+x2_3>=2;
(②③) x1_2+x1_4+x1_6+x2_3+x3_6+x3_4>=2;
(②④) x1_2+x1_6+x3_4+x4_5>=2;
(②①③) x1_6+x1_4+x2_5+x3_4+x3_6>=2;
(②①④) x1_6+x2_3+x2_5+x3_4+x4_5>=2;
(②③④) x1_2+x1_6+x2_3+x3_6+x4_5>=2;
(①②③④)x1_6+x2_5+x3_6+x4_5>=2;

となります。要は、この右側の部分が書き出せればいいのですが、どのように情報をインプットさせて、どのようにループさせていけばいいのか全くわかりません。自分でやってみたのは、
k=1;

for(i=1;i<=C;i++){
if(i==r){
for(j=1;j<=C;j++){
if(c[j]>0&&c[j]!=M){
if(i<j)
printf("+x%d_%d",i,j);
if(i>j)
printf("+x%d_%d",j,i);
}
}
printf(">=%d;\n",HVk[k]);
}
}

for(i=1;i<=C;i++){
if(i!=r&&i!=3&&i!=4){
for(j=1;j<=C;j++){
if(c[[/url][j]>0&&c[[/url][j]!=M&&i!=j){
if(r<j)
printf("+x%d_%d",r,j);
if(r>j)
printf("+x%d_%d",j,r);
}
if(c[j]>0&&c[j]!=M&&r!=j){
if(i<j)
printf("+x%d_%d",i,j);
if(i>j)
printf("+x%d_%d",j,i);
}
}
printf(">=%d;\n",HVk[k]);
}
}
のようなほぼ全列挙のような形なのですが、これだと頂点数が増えたときに場合分けが多すぎてどうしようもなくなってしまうと思います。

何かうまい方法はないでしょうか？ちなみに環境はVista/VisualC++2008です。
つたない説明で意図が伝わるかどうか怪しいですが・・・何卒よろしくお願いします。

グループスタイナーなんてのはわかりませんが、誰からもRESがなさそうなので・・・
たぶん、必要なのは組み合わせパターンを求めることではないかと思いました。
要するにｎ個の中からｒ個を重複無しで取り出すこと（nCr）ではないでしょうか。
ここで、r=1からr=nまですべてを表示すれば良いと思いサンプルを作ってみました。
たぶん、もっと良い方法があるような気がします。まだ、よく考えていないのでとりあえず。

#include <stdio.h>
int v[/url]={1,2,5,6};
int check(int r)
{
	for(int i=1;i<r-1;i++)
		if(v>v[i+1])
			return 1;
	return 0;
}
void disp(int r)
{
	int i;
	for(i=0;i<r;i++)
		printf("%d ",v);
	printf("\n");
}
void swap(int *a,int *b)
{
	int tmp=*a;*a=*b,*b=tmp;
}
void nCr(int n,int r,int i)
{
	if (i < r) {		
		for (int j = i; j < n; j++) {		
			swap(v+i,v+j);			
			nCr(n,r,i+1);			
			swap(v+i,v+j);		
		}	
	}
	else 		
		if(!check(r))
			disp(r);
}
void pairing(int n)
{
	for(int r=1;r<=n;r++)
		nCr(n,r,1);
}	 
int main(void)
{
	pairing(4);
	return 0;
}

ここでは、１，２，５，６の場合（先頭は変更しない）で表示するように作りました。
実行結果は
1
1 2
1 5
1 6
1 2 5
1 2 6
1 5 6
1 2 5 6
になります。
また、int v[/url]={2,1,3,4};にして実行すると
2
2 1
2 3
2 4
2 1 3
2 1 4
2 3 4
2 1 3 4
になります。

返事遅くなりすみません。
自己解決しました。nonさんありがとうございました。