递归的全排列去重算法

本博客声明：http://blog.csdn.net/up_seeker/article/details/8887257

给定任意字符串，求出其全排列

比如：abc

全排列为：abc，acb，bac，bca，cab，cba

只要细心一点，便可发现其规律，每次用一个字符作为首字符，然后对后面的字符求全排列，用递归思想很容易得出其算法（对一个像我这样的编程小菜来说谈何容易？）

这个算法用递归比较简单，但做书上一个题目时要求用迭代方法时，我硬是苦逼了自己一天，最终还是没有写成功，不知道这是不是我没学过算法分析的缘故。

到网上搜索了半天，看到的都是按字典序求解的非递归算法，而且是如此雷同，有其他的也是很复杂的算法，最后我做了一个重大决定——暂时放弃。

此程序主要部分来自《数据结构-C语言版》，注释部分是我对算法的理解，要是我写个非递归的这么容易理解的算法，我肯定第一时间来与君共享之。

/*
* save as perm.c
* 2013-4-29
*/
#include <stdio.h>
#include <string.h>
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
/*去重函数, 这个小测试程序是在网上找非递归算法时发现的*/
int isswap(char *list, int start, int end)	//检查start-end之间有无重复值，有返回0， 无返回1
{
while (start < end) {
if (list[start] == list[end])
return 0; //false
start++;
}
return 1; //true
}
/*全排列的递归函数*/
void perm(char *list, int i, int n)
{
int j, temp;
if (n == i)
//已经递归到最末项，直接输出
printf("%sn", list);
else {
for (j = i; j <= n; j++) {
if (isswap(list, i, j)) {
//检查i--j之间有无重复值，一旦有，则直到后面重复处再去处理
SWAP(list[i], list[j], temp);
//依次将i--j的字符换到i位置处作为头
perm(list, i+1, n);
//将第i+1个位置后面的字符串求全排列，到此进入递归求解
SWAP(list[i], list[j], temp);
//将交换过的字符再换回来
}
}
}
}
int main()
{
char list[10] ;
scanf("%s", list);
perm(list, 0, strlen(list)-1);
printf("n");
return 0;
}

如有大虾愿意就上面的问题给点灵感，将感谢非常！
 

最后

以上就是缥缈季节为你收集整理的递归的全排列去重算法的全部内容，希望文章能够帮你解决递归的全排列去重算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。