blog_name
2012-11-28 22:08 | Lable: Programming |
所有字母排列组合的递归算法 C++

所有字母排列组合的递归算法 C++


本质上是一对一的字母交换。
其实这个可以写成迭代。
事实上也是先写成迭代,再转成递归。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//Permutation
vector<string> permu_r(vector<string> &v_ab_0, unsigned size_r)
{
	string buff(99, '#');
	vector<string> v_ab_buff;
	string o_abcde("abcdefghijklmnopqrstuvwxyz");
	string ab_0;
	v_ab_buff = v_ab_0;
	ab_0.assign(v_ab_0[0].size()+1, '#');
	v_ab_0.clear();
	//skip tab
	for (unsigned ix_1 = 0; ix_1 != v_ab_buff.size(); ++ix_1) {
	for (unsigned ix = 0; ix != ab_0.size(); ++ix) {
		ab_0[0] = o_abcde[ab_0.size()-1];
		for (unsigned iy = 0; iy != ab_0.size(); ++iy) ab_0[iy+1] = v_ab_buff[ix_1][iy];
		buff[ix] = ab_0[0];
		buff[0] = ab_0[ix];
		ab_0[ix] = buff[ix];
		ab_0[0] = buff[0];
		v_ab_0.push_back(ab_0);
	}}
	//recursion way
	return (v_ab_0[0].size() < size_r) ? permu_r(v_ab_0, size_r) : v_ab_0;
}
int main()
{
	//初始化一个最小字母排列组合:ab ba
	vector<string> t_ab;
	t_ab.push_back("ab");
	t_ab.push_back("ba");
	//调用递归函数
	unsigned alpha_bet = 5;//字母长度
	t_ab = permu_r(t_ab, alpha_bet);
	//打印结果
	cout << "Permutation: " << endl;
	for (unsigned ix = 0; ix != t_ab.size(); ++ix) {
		cout << t_ab[ix] << ' ';
		if ((ix+1)%10 == 0) cout << endl;
	}
	cout << endl;
	return 0;
}

输出:
Permutation:
edcab decab cdeab adceb bdcae ecdab cedab dceab acdeb bcdae
eacdb aecdb caedb daceb bacde ebcad becad cbead abced dbcae
edacb deacb adecb cdaeb bdace eadcb aedcb daecb cadeb badce
ecadb ceadb acedb dcaeb bcade ebacd beacd abecd cbaed dbace
edbac debac bdeac adbec cdbae ebdac bedac dbeac abdec cbdae
eabdc aebdc baedc dabec cabde ecbad cebad bcead acbed dcbae
edcba decba cdeba bdcea adcbe ecdba cedba dceba bcdea acdbe
ebcda becda cbeda dbcea abcde eacbd aecbd caebd baced dacbe
edbca debca bdeca cdbea adbce ebdca bedca dbeca cbdea abdce
ecbda cebda bceda dcbea acbde eabcd aebcd baecd cabed dabce
edabc deabc adebc bdaec cdabe eadbc aedbc daebc badec cadbe
ebadc beadc abedc dbaec cbade ecabd ceabd acebd bcaed dcabe
Comments: 0

-
.
评论功能已禁用 |

Previous | Next page | 0-0
0