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

现在的位置: 首页 > 综合 > 正文

RSS

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

2014年01月28日 ⁄ 综合 ⁄ 共 1081字 ⁄ 字号小中大 ⁄ 评论关闭

一：问题描述：

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

二：设计思路：

递归实现，比如字符串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

输出：