前两种是字典序,第三种非字典序。
方法一:组合数学方法 (总结规律,得出结论,偏向数学)
顾名思义,这种方法的思想就是将所有的n元排列按“字典顺序”排成队,以12…n为第一个排列,排序的规则,也就是有一个排列(p)=(p1p2p3…pn)直接生成下一个排列的算法可归结为:
(1)求满足关系式p(k-1)<p(k)的k的最大值,设为i,即i=max{k|p(k-1)<p(k)}
(2)求满足关系式p(i-1)<p(k)的k的最大值,设为j,即j=max{k|p(i-1)<p(k)}
(3)p(i-1)与p(j)互换位置得q=(q1q2...qn)
(4)q=(q1q2...q(i-1)q(i)...qn)中qi...qn部分的顺序逆转,得q1q2...q(i-1)qn...q(i+1)q(i)即为所求的下一个排列。
#include<iostream> using namespace std; bool next_permutation(char* str){ //步骤一 int i = 0; int k = 1; for(k = 1; k < strlen(str); k++){ if(str[k - 1] < str[k]){ i = k; } } if(0 == i){ return 0; } //步骤二 int j = 0; for(k = 0; k < strlen(str); k++){ if(str[i - 1] < str[k]){ j = k; } } //步骤三 str[i - 1] ^= str[j]; str[j] ^= str[i - 1]; str[i - 1] ^= str[j]; //步骤四 k = strlen(str) - 1; while(i < k){ str[i] ^= str[k]; str[k] ^= str[i]; str[i] ^= str[k]; i++; k--; } return 1; } int main(){ char str[10] = "abcde"; int i = 1; while(next_permutation(str)){ cout << str << endl; i++; } cout << i << endl; return 0; }
补充:在C++的STL中也有next_permutation函数。其实现算法就是本算法。
方法二:通过DFS程序设计实现(偏向编程)。
public class Test { public static int N; public static int M; public static int ans = 0; public static int[] flag = new int[1000]; public static void DFS(String str, int depth){ if(depth == M){ System.out.println(str); ans++; return; } int i = 1; for(i = 1; i <= N; i++){ if(0 == flag[i]){ str = str + i; flag[i] = 1; depth++; DFS(str, depth); depth--; flag[i] = 0; str = str.substring(0, str.length() - 1); } } } public static void main(String argus[]) { N = 5; M = 4; DFS("", 0); System.out.println(ans); } }
此程序可以从N个数选M个的所有排列。结果就是字典序。
方法三:递归,每加入一个元素,就将此元素插到之前元素的中间。比如当前字符串"abc",添加'd'后,可以是“abcd”,“abdc”,“adbc”,“dabc”.以此类推。但是此种方法并非是字典序。
#include <stdio.h> #include <string.h> char srcStr[] = "abcde"; void dfs(char* str, int curLen) { char curStr[10]; strcpy(curStr, str); if (curLen == 5) { curStr[5] = '\0'; printf("%s\n", curStr); return; } char ch = srcStr[curLen]; curStr[curLen] = ch; int i = curLen - 1; for (i; i >= 0; i--) { dfs(curStr, curLen + 1); char tmp = curStr[i + 1]; curStr[i + 1] = curStr[i]; curStr[i] = tmp; } dfs(curStr, curLen + 1); } int main() { char curStr[10] = "a"; dfs(curStr, 1); return 0; }