二.去掉重复的全排列的递归实现
由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122,第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了,但对212,它第二个数与第三个数是不相同的,交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。
换种思维,对122,第一个数1与第二个数2交换得到212,然后考虑第一个数1与第三个数2交换,此时由于第三个数等于第二个数,所以第一个数不再与第三个数交换。再考虑212,它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。下面给出完整代码:
// AllRange.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<string>
#include <iostream>
void swap(char* a,char* b)
{
char temp;
temp = *a;
*a=*b;
*b=temp;
}
bool isSwap(char* str,int begin,int end)
{
for(int i=begin;i<end;i++)
{
if(str[i]==str[end])
return false;
}
return true;
}
void AllRange(char* str,int k,int m)
{
if(k == m)
{
printf("%s\n",str);
}
else
{
for(int i=k;i<m;i++)
{
if (isSwap(str,k,i))
{
swap(str+k,str+i);
AllRange(str,k+1,m);
swap(str+k,str+i);
}
}
}
}
void Full(char* str)
{
AllRange(str,0,strlen(str));
}
int _tmain(int argc, _TCHAR* argv[])
{
char str[]="122";
Full(str);
system("pause");
return 0;
}
分享到:
相关推荐
全排列递归算法,在VC下调试OK,递归算法简单快捷,大家理解理解
JAVA递归实现全排列算法,含实现源代码,如a、b、c、d的全排列为: abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc
全排列算法有两个比较常见的实现:递归排列和字典序排列。 (1)递归实现 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典...
山东大学 数据结构实验 全排列 递归练习
递归实现元素全排列
全排列的非递归实现。 输入1,2,3,4 得到 [1 2 3 4]..........[4 3 2 1]所有24种排列
用C语言写的一个递归全排列算法,附有较为详细的注释。
php全排列递归算法代码,需要的朋友可以参考下
全排列-基于递归实现
递归实现元素全排列
全排列:当n==m时,称为全排列; 比如:集合{ 1,2,3}的全排列为: 代码如下: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 我们可以将这个排列问题画成图形表示,即排列枚举树,比如下图为{1,2,3}...
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
不得不说的全排列算法递归实现 我真的是菜啊,留的算法作业几乎没有一次自己写出来过…都是要上网看别人的博客才能懂,自己好笨好菜,
用回溯法递归实现的输出N的全排列 如 123 132 。。。。
自己整理的关于全排列的递归程序.本例以数组{a,b,c}三个元素作为例子详细讲解。里面的程序都经过VC6.0运行通过,请读者放心使用
主要为大家详细介绍了python递归全排列实现方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
全排列-非递归算法(适合动态的新元素加入重新输出全排列-本程序以1到6的数字输出为例)
ackman函数的递归和非递归,学习数据结构的素材,非递归是使用堆栈实现的。