2015年3月25日星期三

给定字符串全排列问题（递归/非递归）

刚才刷微博，看到有人吐槽T大某系GPA第一咖啡馆面试，字符串去重全排列冰淇淋化了都没有搞定。暗笑递归大法好的时候，才看到此题要求非递归，那就谷歌谷歌整理一下吧。

如题，用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 
如 abc 的全排列: abc, acb, bca, dac, cab, cba

一．全排列的递归实现

为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了：

//全排列的递归实现
#include 
#include 
void Swap(char *a, char *b)
{
 char t = *a;
 *a = *b;
 *b = t;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{
 if (k == m)
 {
  static int s_i = 1;
  printf("  第%3d个排列\t%s\n", s_i++, pszStr);
 }
 else
 {
  for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
  {
   Swap(pszStr + k, pszStr + i);
   AllRange(pszStr, k + 1, m);
   Swap(pszStr + k, pszStr + i);
  }
 }
}
void Foo(char *pszStr)
{
 AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
 printf("         全排列的递归实现\n");
 printf("  --by Peikun( http://izpk.blogspot.fr )--\n\n");
 char szTextStr[] = "123";
 printf("%s的全排列如下:\n", szTextStr);
 Foo(szTextStr);
 return 0;
}
运行结果如下：


注意这样的方法没有考虑到重复数字，如122将会输出：

这种输出绝对不符合要求，因此现在要想办法来去掉重复的数列。

二．去掉重复的全排列的递归实现

由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。
换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。下面给出完整代码：

//去重全排列的递归实现
#include 
#include 
#include 
void Swap(char *a, char *b)
{
 char t = *a;
 *a = *b;
 *b = t;
}
//在pszStr数组中，[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{
 for (int i = nBegin; i < nEnd; i++)
  if (pszStr[i] == pszStr[nEnd])
   return false;
 return true;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{
 if (k == m)
 {
  static int s_i = 1;
  printf("  第%3d个排列\t%s\n", s_i++, pszStr);
 }
 else
 {
  for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
  {
   if (IsSwap(pszStr, k, i))
   {
    Swap(pszStr + k, pszStr + i);
    AllRange(pszStr, k + 1, m);
    Swap(pszStr + k, pszStr + i);
   }
  }
 }
}
void Foo(char *pszStr)
{
 AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
 printf("         去重全排列的递归实现\n");
 printf("  --by Peikun( http://izpk.blogspot.fr  )--\n\n");
 char szTextStr[] = "122";
 printf("%s的全排列如下:\n", szTextStr);
 Foo(szTextStr);
 return 0;
}

运行结果如下：


OK，到现在我们已经能熟练写出递归的方法了，并且考虑了字符串中的重复数据可能引发的重复数列问题。那么如何使用非递归的方法来得到全排列了？

三．全排列的非递归实现

要考虑全排列的非递归实现，先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列，全排列的也就迎刃而解了。
如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。
对于像"4321"这种已经是最“大”的排列，采用STL中的处理方法，将字符串整个颠倒得到最“小”的排列"1234"并返回false。
这样，只要一个循环再加上计算字符串下一个排列的函数就可以轻松的实现非递归的全排列算法。按上面思路并参考STL中的实现源码，不难写成一份质量较高的代码。值得注意的是在循环前要对字符串排序下，可以自己写快速排序的代码（请参阅《白话经典算法之六 快速排序 快速搞定》），也可以直接使用VC库中的快速排序函数（请参阅《使用VC库函数中的快速排序函数》）。下面列出完整代码：

//全排列的非递归实现
#include 
#include 
#include 
#include 
void Swap(char *a, char *b)
{
 char t = *a;
 *a = *b;
 *b = t;
}
//反转区间
void Reverse(char *a, char *b)
{
 while (a < b)
  Swap(a++, b--);
}
//下一个排列
bool Next_permutation(char a[])
{
 char *pEnd = a + strlen(a);
 if (a == pEnd)
  return false;
 char *p, *q, *pFind;
 pEnd--;
 p = pEnd;
 while (p != a)
 {
  q = p;
  --p;
  if (*p < *q) //找降序的相邻2数,前一个数即替换数
  {
   //从后向前找比替换点大的第一个数
   pFind = pEnd;
   while (*pFind <= *p)
    --pFind;
   //替换
   Swap(pFind, p);
   //替换点后的数全部反转
   Reverse(q, pEnd);
   return true;
  }
 }
 Reverse(p, pEnd);//如果没有下一个排列,全部反转后返回true
 return false;
}
int QsortCmp(const void *pa, const void *pb)
{
 return *(char*)pa - *(char*)pb;
}
int main()
{
 printf("         全排列的非递归实现\n");
 printf("  --by Peikun( http://izpk.blogspot.fr )--\n\n");
 char szTextStr[] = "abc";
 printf("%s的全排列如下:\n", szTextStr);
 //加上排序
 qsort(szTextStr, strlen(szTextStr), sizeof(szTextStr[0]), QsortCmp);
 int i = 1;
 do{
  printf("第%3d个排列\t%s\n", i++, szTextStr);
 }while (Next_permutation(szTextStr));
 return 0;
}
测试一下，结果如下所示：



将字符串改成"cba"会输出：

至此我们已经运用了递归与非递归的方法解决了全排列问题，总结一下就是：
1．全排列就是从第一个数字起每个数分别与它后面的数字交换。
2．去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。
3．全排列的非递归就是由后向前找替换数和替换点，然后由后向前找第一个比替换数大的数与替换数交换，最后颠倒替换点后的所有数据。

以上主要转载STL系列之十 全排列(百度迅雷笔试题)的内容，代码微调在本地重新实现，图也是我重新截的，调试过程遇到几个问题，如下：

1.'for' loop initial declarations are only allowed in C99 mode
不能在for循环中声明变量。我使用的是codeblocks，默认环境为C94，在Setings -> Complier and debugger settings -> other options中 添加语句“-std=c99”即可解决（注意去掉引号）

2.expected '=', ',', ';', 'asm' or '__attribute__' before IsSwap
可以确定的是，IsSwap前边并不缺乏那些蛋疼的符号，谷歌一下发现有很多雷同问题，但是原因也是千奇百怪：

  • 有可能是漏写；}或者将）写成}，或者是中英文混写，如将英文的)写成中文的）。
  • 机器码本身的问题，需要对数据类型进行typedef，如，使用int类型或者 char类型，分别进行定义，typedef in DTYPE，typedef char PCHAR，这一点没试验过，是看别人的
  • 没有加上需要的头文件
  • C和C++混编，如在C中使用class inline等，需要加上extern告诉编译器。因为C和C++的编译时找不同的内部代码，如果不告诉他，他会找一种，比如说全部找C的内部解释，那么C++部分的就会出错；
  • 明显的错误，比如c代码，结果写了个函数 bool testIt；而bool默认没有定义，所以报错；改成int的就行了；
还以为是什么千奇百怪的头文件...以“bool 声明”关键字搜索发现，缺少了stdbool.h的头文件，加上即可解决

 总结：
去年下半年一直在学函数式编程OCaml，现在思考养成了递归优先的习惯，也是懒。
算法是一条漫长的练级路，吾将左蹦右跳来求索
发帖者 时间：
标签：

没有评论:

发表评论

订阅： 博文评论 (Atom)