务虚笔记

Li Xiaowei's blog


  • 首页

  • 分类

  • 归档

  • 关于

  • 搜索
close
递归产生全排列 | 务虚笔记 - wuxubj,个人博客
务虚笔记

Li Xiaowei's blog


  • 首页

  • 分类

  • 归档

  • 标签

  • 留言

  • 爱的纪念

  • 搜索
close

递归产生全排列

发表于 2016-06-29   |   分类于 算法与数据结构   |  

《数据结构(C语言版)》学习笔记:递归的全排列产生算法(p8)

算法C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void perm(char *list, int begin, int end)
/* 功能:实现字符全排列
/* 参数:
/* list--字符数组,存放需要全排列的元素
/* begin --查找一个排列的开始位置
/* end --查找一个排列的结束位置,当begin=end时,表明完成一个排列
*/

{

if (begin == end)//递归到只有一个数,成功找到一个排列
{
print(list, end);//输出一个全排列
printf("\t");
}
else
{
for (int i = begin; i <= end; i++)//从begin到end依次选取排列首元素
{
swap(list+i, list+begin);//将list[i]与list[begin]交换,即设置为排列首元素
perm(list, begin + 1, end);//递归查找第一个元素之后所有元素的全排列
swap(list + i, list + begin);//完成一次循环之后恢复现场,以保证循环依次遍历不同元素
}
}
}

void print(char *list, int n)
{

for (int i = 0; i <= n; i++)
printf("%c", list[i]);
}
void swap(char *a, char *b)
{

int temp;
temp = *a;
*a = *b;
*b = temp;
}

为什么会有2次交换数据

第一次交换是为了将list[i]设置为排列首元素,第二次交换是为了恢复第一次交换之前的状态,以保证循环依次遍历不同元素。
以序列{a, b, c, d}为例,循环并交换list[i]与list[begin],使a,b,c,d依次为首元素;
以a为首元素,list[0]与list[0]交换,顺序不变;
以b为首元素,list[1]与list[0]交换,顺序变为{b,a,c,d},第一个元素选定之后,对{a,c,d}递归执行全排列,执行完成之后,下一次循环之前,需要将list[1]与list[0]再次交换,以恢复到{a, b, c, d}的顺序,这样,下次循环,再交换list[2]与list[0],才能使得字符c为首元素;
同理可以分析以c和d为首元素的情况。

测试主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<stdlib.h>

void perm(char *list, int begin, int end);
void print(char *list, int n);
void swap(char *a, char *b);

int main()
{

char list[4] = { 'a', 'b', 'c', 'd' };
perm(list, 0, 3);
printf("\n");
system("pause");
return 0;
}
------ 本文结束 ------
wuxubj wechat
扫一扫,用手机访问本站
#算法 #递归 #全排列
魔方构造问题
折半查找
  • 分享到:
  • 微博
  • QQ空间
  • 腾讯微博
  • 微信
  • 文章目录
  • 站点概览
wuxubj

wuxubj

记录敲过的代码、走过的人生

14 日志
7 分类
16 标签
RSS
GitHub Weibo
友情链接
建站日志 学习计划
  1. 1. 算法C语言实现
  2. 2. 为什么会有2次交换数据
  3. 3. 测试主函数
© 2016 wuxubj
由 Hexo 强力驱动
主题 - NexT.Pisces
wuxubj

wuxubj

记录敲过的代码、走过的人生

19 日志
10 分类
26 标签
RSS High
GitHub Weibo
友情链接
建站日志 学习计划
© 2016 - 2017 wuxubj
由 Hexo 强力驱动
主题 - NexT.Pisces
鄂ICP备16017973号
扫二维码
扫一扫,用手机访问本站

扫一扫,用手机访问本站

发送邮件