首页 / 算法 / 排列组合生成算法

排列组合生成算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排列组合生成算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1661字，纯文字阅读大概需要3分钟。

内容图文

 

r排列生成：

gen 递归层数d表示正在生成第d个元素。

vis记录是否出现过。

#include<cstdio>
#include<cstring>
#include<algorithm>
usingnamespace 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);
  }
  elsefor(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);return0;
}

r组合生成，C(n,r) 对应r!个P(n,r)，所以我们按照元素递增的方式来生成相应位置的元素，就能产生C(n,r)

#include<cstdio>
#include<cstring>
#include<algorithm>
usingnamespace 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, intfrom) {
    rer++;
  if(d == r ) {
      cnt++;
      output(r);
  }   
  elsefor(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, intfrom)
{
    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);return0;
}

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

原文：http://www.cnblogs.com/cute/p/3701613.html

内容总结

以上是互联网集市为您收集整理的排列组合生成算法全部内容，希望文章能够帮你解决排列组合生成算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1301405.html

来源：【匿名】