`
cynhafa
  • 浏览: 153102 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

一个很好的字符串全排列算法

 
阅读更多
  1. packagecom.visionsky;
  2. publicclasstest{
  3. privatechar[]numbers=newchar[]{'a','b','c','d','e'};
  4. publicintn;
  5. privateStringlastResult="";
  6. privatebooleanvalidate(Strings){
  7. if(s.compareTo(lastResult)<=0)
  8. returnfalse;
  9. if(s.charAt(2)=='b')
  10. returnfalse;
  11. if(s.indexOf("ce")>=0||s.indexOf("ec")>=0)
  12. returnfalse;
  13. returntrue;
  14. }
  15. /*
  16. *index用于判断当前result中存有字符串的序号
  17. *result当前运行时字符串的结果
  18. */
  19. publicvoidlist(Stringindex,Stringresult){
  20. for(inti=0;i<numbers.length;i++){
  21. if(index.indexOf(i+48)<0){//i+48表示当前i的ascii码,即对i做char型类型转换,判断当前字符是否存在于result中
  22. Strings=result+String.valueOf(numbers[i]);
  23. if(s.length()==numbers.length){
  24. if(validate(s)){
  25. System.out.println(s);
  26. lastResult=s;
  27. n++;
  28. }
  29. break;
  30. }
  31. list(index+String.valueOf(i),s);
  32. }
  33. }
  34. }
  35. publicstaticvoidmain(String[]args){
  36. testt=newtest();
  37. t.list("","");
  38. System.out.println("总数:"+t.n);
  39. }
  40. }

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

字符串的排列

【转】http://zhedahht.blog.163.com/blog/static/254111742007499363479/

题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则输出由字符abc所能排列出来的所有字符串abcacbbacbcacabcba

分析:这是一道很好的考查对递归理解的编程题,因此在过去一年中频繁出现在各大公司的面试、笔试题中。

我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a,求后面两个字符bc的排列。当两个字符bc的排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换,为了保证这次c仍然是和原先处在第一位置的a交换,我们在拿c和第一个字符交换之前,先要把ba交换回来。在交换ba之后,再拿c和处在第一位置的a进行交换,得到cba。我们再次固定第一个字符c,求后面两个字符ba的排列。

既然我们已经知道怎么求三个字符的排列,那么固定第一个字符之后求后面两个字符的排列,就是典型的递归思路了。

基于前面的分析,我们可以得到如下的参考代码:

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;
}
}
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics