- 输入一个字符串， 打印出该字符串中字符的所有排列。举个例子，123的全排列有123、132、213、231、312、321这六种。
- 字符串全排列扩展----八皇后问题
1、思路：
递归思路：全排列就是从第一个数起每一个数分别和他后面数做交换。当数组中有出现重复数字时，当出现之前交换过的数字就跳过，只交换不重复的数字。
Permutation 1 #include2 #include 3 4 using namespace std; 5 6 7 //从第一个数开始，分别与后面的数交换 8 void Permutation1(char* pStr, char* pBegin) 9 {10 assert(pStr && pBegin);11 12 if (*pBegin == '\0')13 printf("%s\n", pStr);14 else15 {16 for (char* pCh = pBegin; *pCh != '\0'; pCh++)17 {18 swap(*pBegin, *pCh);19 Permutation1(pStr, pBegin + 1);20 swap(*pBegin, *pCh);21 }22 }23 }24 25 /**************************************************/26 27 /*如果字符串中有重复的字符则上面的方法有误*/28 //从第一个数开始，分别与后面非重复的数交换29 bool IsSwap(char* pBegin, char* pEnd)30 {31 for (char* p = pBegin; p < pEnd; p++)32 {33 if (*p == *pEnd)34 return false;35 }36 return true;37 }38 39 void Permutation2(char* pStr, char* pBegin)40 {41 assert(pStr && pBegin);42 if (*pBegin == '\0')43 {44 static int num = 1;45 printf("第%d个排列：%s\n", num++, pStr);46 }47 else48 {49 for (char* pCh = pBegin; *pCh != '\0'; pCh++)50 {51 if (IsSwap(pBegin, pCh))52 {53 swap(*pBegin, *pCh);54 Permutation2(pStr, pBegin + 1);55 swap(*pBegin, *pCh);56 }57 }58 }59 }60 61 int main()62 {63 char test[] = "abb";64 Permutation2(test, test);65 }
字典序排列：52431 -> 53421 -> 53124，首先自右向左定位第一个比右侧数小的数2，再从该位置右侧开始遍历最后一个比2大的数字3，然后2和3互换，从该位置右侧一个数字开始逆序，这样就可以得到52431的下一个数字就是53124。
1 #include2 #include 3 #include 4 #include 5 6 #define N 4 7 8 int Cmp(const void *a, const void *b) 9 {10 return *(char*)a - *(char*)b;11 }12 13 void Swp(char *m, char *n)14 {15 char tmp = *m;16 *m = *n;17 *n = tmp;18 }19 20 void Rev(char *str, int m, int n)21 {22 while (m < n)23 {24 Swp(str + m, str + n);25 m++;26 n--;27 }28 }29 30 int Fac(int n)31 {32 assert(n > 0);33 int result = 1, i = 2;34 while (i <= n)35 {36 result *= i;37 i++;38 }39 return result;40 }41 42 void Out(char* str, int len)43 {44 for (int i = 0; i < len; i++)45 printf("%c ", str[i]);46 printf("\n");47 }48 49 void Per(char* str)50 {51 int index1, index2;52 int n = Fac(N);53 for (int i = 1; i < n; i++)54 {55 for (index1 = N - 2; index1 >= 0; index1--)56 {57 if (str[index1] < str[index1 + 1])58 break;59 }60 int min = 32767;61 for (int j = index1 + 1; j < N; j++)62 {63 if (str[j] > str[index1])64 {65 if (str[j] < min)66 {67 min = str[j];68 index2 = j;69 }70 }71 else break;72 }73 Swp(str + index1, str + index2);74 Rev(str, index1 + 1, N - 1);75 Out(str, N);76 }77 }78 79 void main()80 {81 char str[N] = { '1', '2', '4', '3'};82 qsort(str, N, sizeof(char), Cmp);83 Out(str, N);84 Per(str);85 }
2、思路：
行固定，列为全排列问题。保证斜对角的数字符合题目要求就行，所以在打印全排列的时候需要做一个判断。
EightQueen 1 #include2 3 using namespace std; 4 5 int g_number = 0; 6 7 void PrintArray(int* data, int length) 8 { 9 printf("第%d个方案：", g_number);10 for (int i = 0; i < length; i++)11 printf("%d ", data[i]);12 printf("\n");13 }14 15 bool Check(int* cols, int rows)16 {17 for (int i = 0; i < rows; i++)18 {19 for (int j = i + 1; j < rows; j++)20 {21 if (i - j == cols[i] - cols[j] || j - i == cols[i] - cols[j])22 return false;23 }24 }25 return true;26 }27 28 void Permutation(int* cols, int rows, int index)29 {30 if (index == rows)31 {32 if (Check(cols, rows))33 {34 g_number++;35 PrintArray(cols, rows);36 }37 }38 else39 {40 for (int i = index; i < rows; i++)41 {42 swap(cols[index], cols[i]);43 Permutation(cols, rows, index + 1);44 swap(cols[index], cols[i]);45 }46 }47 }48 49 void EightQueen()50 {51 const int rows = 8;52 int cols[rows];53 for (int i = 0; i < rows; i++)54 cols[i] = i;55 Permutation(cols, rows, 0);56 }57 58 int main()59 {60 EightQueen();61 return 0;62 }