配列組合せ生成アルゴリズム

r配列生成:
gen再帰層数dは、d番目の要素が生成されていることを示す.
visレコードが現れたかどうか.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;


int n, r;
int A[50], vis[50];//   i        
int cnt;
int rer;

void output(int r)
{
    for(int i = 0; i < r; i++) printf("%d ", A[i]);
    printf("
");
}

//  P(n, r), r==n ,     
//    d       d     
void gen(int d) {
        rer++;
  if(d == r ) {
          cnt++;
          output(r);
  }
  else for(int i = 0; i < n; i++)
    if(!vis[i]) {
      A[d] = i;
      vis[i] = 1;
      gen(d+1);
      vis[i] = 0;
    }
}

void gen1(int d)
{
        for(int i=0;i<n;i++)
        {
                if(!vis[i])
                {
                        vis[i]=1;
                        A[d]=i;
                        if(d==r-1)
                                output(r);
                        else
                                gen1(d+1);
                        vis[i]=0;
                }
        }
}

int main() {
  scanf("%d%d", &n, &r);
  memset(vis, 0, sizeof(vis));
  gen(0);
  gen1(0);
  //printf("%d
", cnt);
  //printf("%d
", rer);
  return 0;
}

rコンビネーション生成、C(n,r)対応r!個のP(n,r)があるので,要素をインクリメントすることで対応する位置の要素を生成し,C(n,r)を生成することができる.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;


int n, r;
int A[50], vis[50];//   i        
int cnt;
int rer;

void output(int r)
{
    for(int i = 0; i < r; i++) printf("%d ", A[i]);
    printf("
");
}

//  C(n, r), 
//    d       d     
void gen(int d, int from) {
    rer++;
  if(d == r ) {
      cnt++;
      output(r);
  }   
  else for(int i = from; i < n; i++)
    if(!vis[i]) {
      A[d] = i; 
      vis[i] = 1;
      gen(d+1, i+1);
      vis[i] = 0;
    } 
}   

void gen1(int d, int from)
{
    for(int i=from;i<n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            A[d]=i;
            if(d==r-1)
                output(r);
            else
                gen1(d+1, i+1);
            vis[i]=0;
        }
    }
}

int main() {
  scanf("%d%d", &n, &r);
  memset(vis, 0, sizeof(vis));
  //gen(0, 0);
  gen1(0, 0);
  //printf("%d
", cnt);
  //printf("%d
", rer);
  return 0;
}

参考:プログラム設計における組合せ数学