| 务虚笔记 - wuxubj,个人博客

算法C语言实现

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为首元素的情况。

测试主函数

#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;
}