全排列属于组合数学的知识,有序数法,字典序法,临位互换法,本文着重从字典序法(stl中的Next_permutation也是使用此法)对字符串s进行全排列。具体算法如下:
I)从后往前找到第一个j,使得s[j]<s[j+1]，若未找到，即j=-1时结束
II)从后往前找到第一个k,使得s[k] > s[j],然后交换s[k],s[j]
III)将s[j+1:n]倒置
对于这种算法是如何得到全排列的证明如下:
1.子串s[j+1:n]是单调递减的,即对于前半部分为s[0:j]的当前字符串而言，后半部分是全排列的最大值
2.s[k]是从后往前找到的第一个大于s[j]的字符,所以交换后,得到的字符串是下一轮排列的最大值
故只要将s[j+1:n](交换后)倒置即得到next_permutation
#include <stdio.h> #include <string.h> #define swap(a,b){char tmp=a;a=b;b=tmp;} //a=a+b;b=a-b;a=a-b; #define N 50 void Permutation(char *s){ int i,j,k; while(1){ puts(s); for(j = strlen(s) - 2 ; j >= 0 ; j --) if(s[j] < s[j+1]){ //第一个比右边小 break; } if(j == -1) break; //已得到最大全排列 for(i = strlen(s) - 1 ; i >= 0 ; i -- ) if(s[i] > s[j]){ swap(s[i],s[j]); break; //need break } for(i = j + 1 ; i <= (strlen(s)-1+j)/2 ; i ++ ) //从j开始的子串倒置,need"=" swap(s[i],s[strlen(s)+j-i]); } } int main(){ char s[N] = "1234"; Permutation(s); return 0; }
显然,我们注意到字典序法适用于:无重复但需要初始状态按ascii码升序字符串全排列
对于存在重复的字符串以及有序数法和临位互换法的实现将在以后的文章中讲解。。。
参考资料:
http://blog.csdn.net/cpfeed/article/details/7376132
原文：http://www.cnblogs.com/520xiuge/p/6414521.html