Chinaunix首页 | 论坛 | 博客

Linux爱好者angrad.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

angrad

  • 博客访问： 481954
  • 博文数量： 59
  • 博客积分： 345
  • 博客等级： 二等列兵
  • 技术积分： 1380
  • 用 户 组： 普通用户
  • 注册时间： 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文（59）

文章存档

2017年（5）

2013年（47）

2012年（3）

2011年（4）

我的朋友
最近访客
推荐博文
相关博文
递归求解排列和组合

分类： C/C++

2013-03-03 11:42:05

/*类循环排列*/
Input:
3 2
Output:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

点击(此处)折叠或打开

  1. #include <stdio.h>

  3. #define MAX 10

  5. int rcd[MAX];
  6. int n, m; //n位数，有0-m-1数字构成

  8. void loop_permutation(int l)
  9. {
  10.     int i;
  11.     if(l == n)
  12.     {
  13.         for(i=0; i<n; i++)
  14.         {
  15.             printf("%d", rcd[i]);
  16.             if(i < l-1)
  17.             {
  18.                 printf(" ");
  19.             }
  20.         }
  21.         printf("n");
  22.         return ;
  23.     }
  24.     for(i=0; i<m; i++)
  25.     {
  26.         rcd[l] = i;
  27.         loop_permutation(l+1);
  28.     }
  29. }

  31. int main()
  32. {
  33.     while(scanf("%d %d", &n, &m) == 2)
  34.     {
  35.         loop_permutation(0);
  36.     }
  37.     return 0;
  38. }

--------------------------------------------------

/*全排列*/
Input:
3
1 2 3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX 10

  6. int rcd[MAX];
  7. int used[MAX];
  8. int num[MAX];
  9. int n;

  11. void full_permutation(int l)
  12. {
  13.     int i;
  14.     if(l == n)
  15.     {
  16.         for(i=0; i<n; i++)
  17.         {
  18.             printf("%d", rcd[i]);
  19.             if(i < n-1)
  20.             {
  21.                 printf(" ");
  22.             }
  23.         }
  24.         printf("n");
  25.         return ;
  26.     }
  27.     for(i=0; i<n; i++)
  28.     {
  29.         if(!used[i])
  30.         {
  31.             used[i] = 1;
  32.             rcd[l] = num[i];
  33.             full_permutation(l+1);
  34.             used[i] = 0;
  35.         }
  36.     }
  37. }

  39. int main()
  40. {
  41.     int i;
  42.     while(scanf("%d", &n) != EOF)
  43.     {
  44.         for(i=0; i<n; i++)
  45.         {
  46.             scanf("%d", &num[i]);
  47.         }
  48.         memset(used, 0, sizeof(used));
  49.         full_permutation(0);
  50.     }
  51.     return 0;
  52. }


--------------------------------------------------

/*不重复全排列*/
Input:
3
1 1 2
Output:
1 1 2
1 2 1
2 1 1
 

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX 10

  6. int rcd[MAX];
  7. int used[MAX];
  8. int num[MAX]; //存放互不相同的m个数
  9. int n, m; //n个数，互不相同有m个

  11. void unrepeat_full_permutation(int l)
  12. {
  13.     int i;
  14.     if(l == n)
  15.     {
  16.         for(i=0; i<n; i++)
  17.         {
  18.             printf("%d", rcd[i]);
  19.             if(i < n-1)
  20.             {
  21.                 printf(" ");
  22.             }
  23.         }
  24.         printf("n");
  25.         return ;
  26.     }
  27.     for(i=0; i<n; i++)
  28.     {
  29.         if(used[i] > 0)
  30.         {
  31.             used[i]--;
  32.             rcd[l] = num[i];
  33.             unrepeat_full_permutation(l+1);
  34.             used[i]++;
  35.         }
  36.     }
  37. }

  39. int main()
  40. {
  41.     int i, j, val;
  42.     while(scanf("%d", &n) != EOF)
  43.     {
  44.         m = 0;
  45.         memset(used, 0, sizeof(used));
  46.         for(i=0; i<n; i++)
  47.         {
  48.             scanf("%d", &val);
  49.             for(j=0; j<m; j++)
  50.             {
  51.                 if(num[j] == val)
  52.                 {
  53.                     used[j]++;
  54.                     break;
  55.                 }
  56.             }
  57.             if(j == m)
  58.             {
  59.                 num[m] = val;
  60.                 used[m++] = 1;
  61.             }
  62.         }
  63.         unrepeat_full_permutation(0);
  64.     }
  65. }

--------------------------------------------------

/*组合*/
Input:
4 3
1 2 3 4
Output:
1 2 3
1 2 4
1 3 4
2 3 4
 

点击(此处)折叠或打开

  1. #include <stdio.h>

  3. #define MAX 10

  5. int rcd[MAX];
  6. int num[MAX];
  7. int n, m; //从n个数中选m个数

  9. void select_combination(int l, int z)
  10. {
  11.     int i;
  12.     if(l == m) //已选m个数
  13.     {
  14.         for(i=0; i<m; i++)
  15.         {
  16.             printf("%d", rcd[i]);
  17.             if(i < m-1)
  18.             {
  19.                 printf(" ");
  20.             }
  21.         }
  22.         printf("n");
  23.         return ;
  24.     }
  25.     for(i=z; i<n; i++) //上次为num[z-1],此次从num[z]开始
  26.     {
  27.         rcd[l] = num[i];
  28.         select_combination(l+1, i+1); //i+
  29.     }
  30. }

  32. int main()
  33. {
  34.     int i;
  35.     while(scanf("%d %d", &n, &m) != EOF)
  36.     {
  37.         for(i=0; i<n; i++)
  38.         {
  39.             scanf("%d", &num[i]);
  40.         }
  41.         select_combination(0, 0);
  42.     }
  43.     return 0;
  44. }


--------------------------------------------------

/*全组合*/
Input:
3
1 2 3
Output:
1
1 2
1 2 3
1 3
2
2 3
3
 

点击(此处)折叠或打开

  1. #include <stdio.h>

  3. #define MAX 10

  5. int rcd[MAX];
  6. int num[MAX];
  7. int n;

  9. void full_combination(int l, int z)
  10. {
  11.     int i;
  12.     for(i=0; i<l; i++)
  13.     {
  14.         printf("%d", rcd[i]);
  15.         if(i < l-1)
  16.         {
  17.             printf(" ");
  18.         }
  19.     }
  20.     printf("n");
  21.     for(i=z; i<n; i++) //i=
  22.     {
  23.         rcd[l] = num[i];
  24.         full_combination(l+1, i+1);
  25.     }
  26. }

  28. int main()
  29. {
  30.     int i;
  31.     while(scanf("%d", &n) != EOF)
  32.     {
  33.         for(i=0; i<n; i++)
  34.         {
  35.             scanf("%d", &num[i]);
  36.         }
  37.         full_combination(0, 0);
  38.     }
  39.     return 0;
  40. }

--------------------------------------------------

/*不重复组合*/
Input:
3
1 1 3
Output:
1
1 1
1 1 3
1 3
3

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX 10

  6. int rcd[MAX];
  7. int num[MAX];
  8. int used[MAX];
  9. int n, m; //n个数中有m个不同的数

  11. void unrepeat_combination(int l, int z)
  12. {
  13.     int i;
  14.     for(i=0; i<l; i++)
  15.     {
  16.         printf("%d", rcd[i]);
  17.         if(i < l-1)
  18.         {
  19.             printf(" ");
  20.         }
  21.     }
  22.     printf("n");
  23.     for(i=z; i<m; i++)
  24.     {
  25.         if(used[i] > 0)
  26.         {
  27.             used[i]--;
  28.             rcd[l] = num[i];
  29.             unrepeat_combination(l+1, i); //l+
  30.             used[i]++;
  31.         }
  32.     }
  33. }

  35. int main()
  36. {
  37.     int i, j, val;
  38.     while(scanf("%d", &n) != EOF)
  39.     {
  40.         m = 0;
  41.         memset(used, 0, sizeof(used));
  42.         for(i=0; i<n; i++)
  43.         {
  44.             scanf("%d", &val);
  45.             for(j=0; j<m; j++)
  46.             {
  47.                 if(num[j] == val)
  48.                 {
  49.                     used[j]++;
  50.                     break;
  51.                 }
  52.             }
  53.             if(j == m)
  54.             {
  55.                 num[m] = val;
  56.                 used[m++] = 1;
  57.             }
  58.         }
  59.         unrepeat_combination(0, 0);
  60.     }
  61.     return 0;
  62. }

2011-05-12 18:23  发表于百度空间，今搬至CU。
阅读(1576) | 评论(0) | 转发(1) |
0

上一篇：基姆拉尔森计算 “某天是星期几”

下一篇：优于KMP算法的 BM改进算法——SUNDAY算法

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6