首页 > 代码库 > 排列组合生成算法

排列组合生成算法

2024-07-02 05:57:08   240人阅读

 

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("\n");
}

//生成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\n", cnt);
  //printf("%d\n", 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("\n");
}

//生成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\n", cnt);
  //printf("%d\n", rer);
  return 0;
}

参考：程序设计中的组合数学


联系
我们