算法|算法 —— 字符串的全排列和组合算法|C知识总结

一、字符串的全排列 && 递归
二、字符串的全排列 && 去重 && 递归
三、字符串的全排列 && 去重 && 非递归
四、字符串的组合 && 递归

【算法|算法 —— 字符串的全排列和组合】
一、字符串的全排列 && 递归题目：实现一个函数，打印出字符串pStr的全排列。例如，”abc”的全排列：”abc”, “acb”, “bca”, “dac”, “cab”, “cba”。

void Permutation1(char *pStr) { if (nullptr == pStr) return; Permutation1(pStr, pStr); }void Permutation1(char* pStr, char* pBegin) { if ('\0' == *pBegin) { printf("%s\n", pStr); } else { char *pCh = pBegin; for (; *pCh != '\0'; ++pCh) { swap(*pCh, *pBegin); Permutation1(pStr, pBegin + 1); swap(*pCh, *pBegin); } } }

二、字符串的全排列 && 去重 && 递归

void Permutation2(char *pStr) { if (nullptr == pStr) return; Permutation2(pStr, pStr); }bool IsSwap(char* pBegin, char* pEnd) { char* pCh = pBegin; for (; pCh < pEnd; ++pCh) { if (*pCh == *pEnd) return false; } return true; }void Permutation2(char* pStr, char* pBegin) { if ('\0' == *pBegin) { printf("%s\n", pStr); } else { char *pCh = pBegin; for (; *pCh != '\0'; ++pCh) { // 每个元素和它后面非重复的元素进行交换 if (IsSwap(pBegin, pCh)) { swap(*pCh, *pBegin); Permutation2(pStr, pBegin + 1); swap(*pCh, *pBegin); } } } }

三、字符串的全排列 && 去重 && 非递归

bool Next_permutation(char* pStr) { // 空串 assert(pStr != nullptr); // 标记字符串最后一个字符的下一个位置 char* pEnd = pStr + strlen(pStr); char* i = pStr; if (++i == pEnd) //只有一个元素 return false; i = pEnd; --i; // i 指向最后一个字符for (; ; ) { char* ii = i; --i; //上面(i, ii)就是两个相邻的字符if (*i < *ii) //前一个字符小于后一个字符 { char* j = pEnd; // 指向尾端 while (*i >= *--j); // 一直往前找，找到比 *i 大的字符 swap(*i, *j); // 交换i，j reverse(ii, pEnd); // 把ii后面的元素全部逆置 return true; } if (i == pStr)// 找到最前面了 { reverse(pStr, pEnd); //把整个字符串逆置回来（恢复至初始状态） return false; } } }

四、字符串的组合 && 递归

void Combination(char *string) { assert(string != NULL); vector result; int i = 0; int length = strlen(string); for (i = 1; i <= length; ++i) Combination(string, i, result); }void Combination(char *string, int number, vector &result) { assert(string != NULL); if (number == 0) { static int num = 1; printf("第%d个组合\t", num++); vector::iterator iter = result.begin(); for (; iter != result.end(); ++iter) printf("%c", *iter); printf("\n"); return; } if (*string == '\0') return; result.push_back(*string); Combination(string + 1, number - 1, result); result.pop_back(); Combination(string + 1, number, result); }