字符串全排列算法--去除重复的排列

一：问题描述：

输入一字符串，显示其非重复的全排列

二：设计思路：

递归实现，比如字符串abb，设计一个指针pBegin指向当前被操作的字符，定义一个新指针it从pBegin位置开始，与pBegin所指向字符交换

比如：输入abb

pBegin指向首字符a，it从pBgin位置开始与其所指向字符交换

三 ：代码

/*This is a free Program, You can modify or redistribute it under the terms of GNU*Description:字符串全排列--去除重复的排列*Language: C++*Development Environment: VC6.0*Author: Wangzhicheng*E-mail: 2363702560@qq.com*Date: 2012/12/12*/#include <iostream>#include <string>#include <algorithm>using namespace std;class Solution {private:string str;    /*检验pBegin到pEnd区间内有没有和*pEnd相同的字符*/bool IsSwap(string::iterator pBegin,string::iterator pEnd) {string::iterator it;for(it=pBegin;it!=pEnd;it++) {if(*it==*pEnd) return false;}return true;}/*递归实现全排列,要想除去重复的排列,关键在于理解递归的过程*/void FullArrange(string &str,string::iterator pBegin) {static int i;if(!(*pBegin)) {cout<<"第"<<++i<<"种全排列是:"<<str<<endl;}else {for(string::iterator it=pBegin;*it;it++) {if(!IsSwap(pBegin,it)) continue;swap(*pBegin,*it);FullArrange(str,pBegin+1);swap(*pBegin,*it);}}}public:Solution(const string str) {this->str=str;}void FullArrange() {FullArrange(str,str.begin());}};void main() {Solution s("abb");s.FullArrange();}

三：测试

输入abb

输出：

输入abcd

输出：