前言
其实这个算法已经用PHP实现了,详细请看这篇文章:PHP排列组合算法(支持任意字典)
今天我们就用C/C++来实现这个算法
(变得更简单了)
C++
感慨一下:使用C++实现这个算法真的好用(vector YYDS)。
引用库
- <string>
- <vector>
C++部分我们使用面向对象编程来编写,分为2个文件
main.h
#include <string> #include <vector> class StringCombination { private: std::vector<std::string> stringsDict; std::pair<std::string, int> term; int dictLength; ssize_t valueLength = -1; public: StringCombination(const std::vector<std::string> &strings, int length = -1) : stringsDict(strings), dictLength(strings.size()), valueLength(length) { term.first = stringsDict[0]; term.second = stringsDict[0].length(); } std::string nextValue(std::string value); };
main.cpp
#include "main.h" std::string StringCombination::nextValue(std::string value) { if (value.empty()) value = ""; int i = 0, dictOrder; std::vector<std::pair<std::string, int>> nextValueCut; std::string temp; while (value.length() > i) { dictOrder = -1; for (size_t n = 0; n < dictLength; n++) { term.first = stringsDict[n]; term.second = stringsDict[n].length(); temp = value.substr(i, term.second); if (temp == term.first) { i += term.second - 1; dictOrder = n; break; } } ++i; nextValueCut.push_back({temp, dictOrder}); } bool carry = false; bool closeCarry = false; bool handlerEnd = false; bool addLength = true; ssize_t countCarry = 0; for (ssize_t n = nextValueCut.size() - 1; n >= 0; n--) { if (nextValueCut[n].second == -1) continue; if (nextValueCut[n].second == dictLength - 1) { if (!handlerEnd || carry) carry = true; nextValueCut[n].second = 0; } else { ++nextValueCut[n].second; if (carry) closeCarry = true; } if (!handlerEnd) handlerEnd = true; else if (!carry) continue; nextValueCut[n].first = stringsDict[nextValueCut[n].second]; if (closeCarry) { carry = false; closeCarry = false; } if (!carry) { addLength = false; break; } ++countCarry; } if (valueLength != -1 && countCarry >= valueLength) addLength = false; std::string result = ""; if (addLength) { result += stringsDict[0]; } for (ssize_t n = 0; n < nextValueCut.size(); n++) { result += nextValueCut[n].first; } return result; }
示例
#include "main.cpp" #include <iostream> int main() { std::vector<std::string> dict = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" }; StringCombination stringCombination(dict); std::string nowValue = "aaa"; for (size_t i = 0; i < 1000; i++) { nowValue = stringCombination.nextValue(nowValue); std::cout << nowValue << "\n"; } return(0); }
C
使用C语言实现这个就相对来说比较复杂了
引用库
- <string.h>
- <stdlib>
- <stdbool>
可以用下面的代码代替
typedef int bool; #define true 1 #define false 0
代码
可以看见这是个静态函数,你也可以删掉static关键字,使其成为普通函数
这个支持任意字符字典
static char *nextValue(char *value, const char *stringsDict, int maxLength) { int valueLength = strlen(value); if (valueLength == 0) value = ""; typedef struct EchoWord { char value; int location; } Word; int i = 0, add = 0, dictOrder, dictLength = strlen(stringsDict); long n; Word term = {stringsDict[0], 0}; Word *nextValueCut = (Word *)malloc(sizeof(Word) * valueLength); char *result = (char *)malloc(sizeof(char) * (valueLength + 1)); char *tempMalloc = NULL; char temp; if (!nextValueCut) { result[0] = '\0'; goto Clear; } if (!result) { result[0] = '\0'; goto Clear; } for (i = 0; i < valueLength; i++) { dictOrder = -1; for (n = 0; n < dictLength; n++) { term.value = stringsDict[n]; temp = value[i]; if (temp == term.value) { dictOrder = n; break; } } nextValueCut[i].value = temp; nextValueCut[i].location = dictOrder; } bool carry = false; bool closeCarry = false; bool handlerEnd = false; bool addLength = true; long countCarry = 0; for (long n = valueLength - 1; n >= 0; n--) { if (nextValueCut[n].location == -1) continue; if (nextValueCut[n].location == dictLength - 1) { if (!handlerEnd || carry) carry = true; nextValueCut[n].location = 0; } else { ++nextValueCut[n].location; if (carry) closeCarry = true; } if (!handlerEnd) handlerEnd = true; else if (!carry) continue; nextValueCut[n].value = stringsDict[nextValueCut[n].location]; if (closeCarry) { carry = false; closeCarry = false; } if (!carry) { addLength = false; break; } ++countCarry; } if (maxLength != -1 && countCarry >= maxLength) addLength = false; if (addLength) { tempMalloc = (char *)malloc(sizeof(char)); if (tempMalloc) { result = (char *)realloc(tempMalloc, sizeof(char) * (++valueLength + 1)); } if (!result) goto Clear; result[0] = stringsDict[0]; ++add; } for (n = 0; n < valueLength - add; n++) { result[n + add] = nextValueCut[n].value; } result[valueLength] = '\0'; Clear: free(nextValueCut); return result; }
示例
#include <string.h> #include <stdlib.h> #include <stdbool.h> #include <stdio.h> //函数放这里 int main() { char* dict = "abcdefg"; char* now = "aa"; long i; for (i = 0; i < 1000; i++) { now = nextValue(now, dict, -1); printf("%s\n",now); } return(0); }
总结
这是用C/C++排列组合算法(支持任意字典),比较简单,有问题请在评论区留言
(什么?没有注释?ᓚᘏᗢ)