Announce

PukiWiki contents have been moved into SONOTS Plugin (20070703)

Algorithm

グラフのすべてのサブグラフの取得(すべての組み合わせ)

各頂点のあるなしをビットに置き換える。
そうすれば2進表記でループをまわせる。
n=8なら、
00000000から11111111までループさせればOK
ループの中でどのビットが立ってるか計算して完全グラフかどうか判定汁

Pseudo code
/* All combinations (subgraphs) of n vertices graph can be expressed by n bits integer, e.g. when n=8, all subgraphs can be expressed by looping from 00000000 to 11111111 and judging which bits are 1. */

bool G[n][n];     /* graph */
int S[n];         /* A set of vertices expressing a subgraph */
int max=0;       /* maximum size of cliques */
for( i=0; i<2^n ; i++)
{
  int k = 0;
  bool flag = true;
  for( j=0; j<n; j++)
  {
      if( i & ( 1 << j ) )
      {
         [kS++]= j ;
      }
  }
  for( j=0; j < k; j++)
  {
     for( l=j+1; l<k; l++)
     {
	  if( j == l ) continue;
         if( !G[ S[j] ][ S[l] ] ) flag = false;
         if( !flag ) break;
     }
     if( !flag ) break;
  }
  if( flag ){
	if(max < k)
	{
		max=k;
	}
   }
}

n 個から k 個を選ぶすべての組み合わせ

再帰 (この時点で O(n^n)。上のは 2^n までのループなので 上のを使って削ったほうが 2^n 以下になるのでまだいいはず)
組み合わせの配列をつくるわけではない。このテンプレートの中に組み込む

int data[n]; /* 1,2,3,4...n などの数字から選ぶ場合は配列はいらないだろう */
bool visited[n];
for(int i=0; i<n ; i++)
{
   comb(i);
}

void comb(int v){
   visited[v]=TRUE;
   for(int i=0; i<n; i++)
   {
      if( visited[i] ) num++;
   }
   if( num >= k ){
       for(int i=0; i<n; i++) 
          if ( visited[i] )
              data[i] hogehoge

       return;
   }

   for(int i=0; i<n; i++)
   {
     if( !visited[v] )
     {
        comb(i); 
     }
   }
   visited[v] = FALSE;
   return;
}