- packagecom.visionsky;
- publicclasstest{
- privatechar[]numbers=newchar[]{'a','b','c','d','e'};
- publicintn;
- privateStringlastResult="";
- privatebooleanvalidate(Strings){
- if(s.compareTo(lastResult)<=0)
- returnfalse;
- if(s.charAt(2)=='b')
- returnfalse;
- if(s.indexOf("ce")>=0||s.indexOf("ec")>=0)
- returnfalse;
- returntrue;
- }
- publicvoidlist(Stringindex,Stringresult){
- for(inti=0;i<numbers.length;i++){
- if(index.indexOf(i+48)<0){
- Strings=result+String.valueOf(numbers[i]);
- if(s.length()==numbers.length){
- if(validate(s)){
- System.out.println(s);
- lastResult=s;
- n++;
- }
- break;
- }
- list(index+String.valueOf(i),s);
- }
- }
- }
- publicstaticvoidmain(String[]args){
- testt=newtest();
- t.list("","");
- System.out.println("总数:"+t.n);
- }
- }
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【转】http://zhedahht.blog.163.com/blog/static/254111742007499363479/
题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
分析:这是一道很好的考查对递归理解的编程题,因此在过去一年中频繁出现在各大公司的面试、笔试题中。
我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a,求后面两个字符bc的排列。当两个字符bc的排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换,为了保证这次c仍然是和原先处在第一位置的a交换,我们在拿c和第一个字符交换之前,先要把b和a交换回来。在交换b和a之后,再拿c和处在第一位置的a进行交换,得到cba。我们再次固定第一个字符c,求后面两个字符b、a的排列。
既然我们已经知道怎么求三个字符的排列,那么固定第一个字符之后求后面两个字符的排列,就是典型的递归思路了。
基于前面的分析,我们可以得到如下的参考代码:
void Permutation(char* pStr,
char* pBegin);
/////////////////////////////////////////////////////////////////////////
// Get the permutation of a string,
// for example, input string abc, its permutation is
// abc acb bac bca cba cab
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr)
{
Permutation(pStr, pStr);
}
/////////////////////////////////////////////////////////////////////////
// Print the permutation of a string,
// Input: pStr
- input string
//
pBegin - points to the begin char of string
//
which we want to permutate in this recursion
/////////////////////////////////////////////////////////////////////////
void Permutation(char* pStr,
char* pBegin)
{
if(!pStr || !pBegin)
return;
// if pBegin points to the end of string,
// this round of permutation is finished,
// print the permuted string
if(*pBegin == '\0')
{
printf("%s\n", pStr);
}
// otherwise, permute string
else
{
for(char* pCh = pBegin; *pCh !=
'\0'; ++ pCh)
{
// swap pCh and pBegin
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
// restore pCh and pBegin
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
分享到:
相关推荐
主要介绍了Python字符串的全排列算法,结合实例形式较为详细的总结分析了Python字符串全排列的常见操作技巧,需要的朋友可以参考下
Java写的源码,解决各种字符串全排列问题,已解决重复问题,经过上机调试可直接运行
自己写的基于字符的全排列算法,代码简洁,高效,7位数的全排列都是秒排!用到了广度优先排列,深度优先搜索和几个递归,唯一没完成的是退出时释放内存,呵呵,破解密码时超有用的哟,,
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
可以打印出字符串的全排列,代码是C语音风格的,刚学习编程时写的代码
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba 思路 这是典型的递归求解问题,递归算法有四个特性: 必须有可...
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
全排列算法: 比如字符串abc,全排列结果为abc,acb,bac,bca,cba,cab。
CC++全排列..1--n的全排列以及字符串的全排列
基于Qt写了一个字符串加密的算法模块(有源码),并封装成了动态库,有测试用例。实现的加密解密算法是AES加密对称算法和BlowFish。用户可以直接用动态库,也可以用源码编译。
带通配符的字符串匹配算法,带通配符的字符串匹配算法
关于经典算法--压缩字符串(将字符串内连续重复出现的字符进行压缩),个人的想法
字符串匹配算法之Horspool算法(英文原版)
输出有重复字符的全排列,C++源码......
KMP字符串匹配算法,一种快速模式匹配算法
字符串的全排列和组合算法.doc
首先对三种基本字符串匹配算法进行了详细分析和说明,再编程实现。创新拓展研究了Boyer-Moore算法,进行了分析和编程实现。让四种算法对数据量极大的文本,进行子串的查询处理,并分析算法运行时间效率,并对所有...
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
常见的字符串匹配算法及实现