了解 C++ STL的全排列函数
首先, 对于全排列算法
, C++ STL提供了next_permutation(begin, end)函数, 使用该函数可以按字典序
来获得全排列中的下一个排列
.
只需要循环调用该函数, 即可获得所有的全排列情况
注意: next_permutation()函数对支持迭代器的容器均使用, 可以直接用于string类, 也可以用于 数组(需传入指针).
读读题目, 了解需求
根据题目要求, 需要我们用一组字母
按组成符合条件的密码
可以得出以下信息:
(条件1) 有效的密码 均由 小写字母组成
(条件2) 有效的密码 至少包含1个元音字母 + 至少包含2个辅音字母
(条件3) 有效的密码 必须符合 字典序
(条件4) 一组字母 里的字母不可以被重复使用.
(条件5) 最终的输出结果列表, 也要求按字典序输出.
(条件6) 密码要求L位数
考虑到最终的输出结果也必须要按字典序输出
这个条件, 我们不妨直接在 算法阶段 就按字典序来进行密码构造
,这样就方便很多了。(其实这个 按字典序输出 有些暗示
的意义了, 大概知道这里需要进行全排列.)
放宽条件: 获得”全部的密码列表”
对于条件1
,很容易进行满足,我们只需要保证输入和算法处理时,都使用小写字母即可(不要用大写字母和小写字母混杂,否则字典序处理会引入新的麻烦)
对于条件3
,我们可以在构造密码
阶段就按字典序来构造,也就是使用我们上面所说的next_permutation()函数
, 因为这个全排列算法
是按字典序
来进行排列的。在构造密码时就满足条件3
的话,自然条件5
也就满足了。
结合条件3
和条件4
,我们将使用一串字母
来构造字符串,然后对这个字符串进行按字典序排列
得到基础字符串
如: 一串字母"a t c i s w"
可以构造字符串"atcisw"
,然后对该字符串进行按字典序排列可得到基础字符串acistw
,接下来,我们只需要对基础字符串
运行next_permutation()函数
即可得到由这一串字母按字典序排列的所有可能的密码
据此,到这一步,我们获得的密码列表中,并非所有的密码都是有效的密码
。
但是,我们可以肯定,有效的密码列表
是全部的密码列表
的1个子集,且由于全部的密码列表
里的密码
是按字典序
列出的,所以,我们只需要对全部的密码列表
过滤掉一些无效的密码
,即可获得有效的密码列表
。
这个有效的密码列表
也就是最终的答案
了。
限制条件: 过滤”全部的密码列表”得”有效的密码列表”
根据条件6
, 要求密码的长度为指定的L位, 我们只需要对密码
进行截短
即可得到L位长度的密码
然后再根据条件2
,我们可以编写1个简单的 判断函数,在全部的密码列表
中剔除掉这些 元音和辅音字母不满足的密码
到这一步,我们已经得到了有效的密码列表
了,
只需要按顺序输出该列表里的所有密码
即可
注意:在输出有效的密码列表
时,要注意重复的字符串
的问题,因为我们之前进行截短字符串
,导致可能的字符串重复
,对于重复字符串
,只需要输出1次即可。(需要稍微记录下,哪些字符串重复过,以便在输出时进行判断。)
回顾流程
在整个题目中,虽然要求我们构造 满足多个条件限制的密码。
但是,我们人为地放宽了条件
,以此来得到最终答案
的超集
。
紧接着,我们再引入条件
,来获得最终答案
总体流程:
根据一组字母
-> 构造基础字符串
-> 对基础字符串
运行next_permutation()获得全部的密码列表
(已按字典序排列) -> 在全部的密码列表
里截短
密码 -> 在全部的密码列表
中过滤掉不符合元音辅音字母要求的密码
-> 按顺序输出全部的密码列表
里的密码 (去重输出)
CODE
需include stdio.h, stdlib.h, algorithm, vector, set, map, string, iostream #pragma warning (disable:4996) using namespace std; bool limitC(string psw) { int vowelCnt = 0; int consonantCnt = 0; for (int i = 0; i < psw.size(); i++) { if (psw[i] == 'a' || psw[i] == 'e' || psw[i] == 'i' || psw[i] == 'o' || psw[i] == 'u') { vowelCnt++; } else { consonantCnt++; } } return vowelCnt >= 1 && consonantCnt >= 2 ? true : false; } int main() { int L, C; scanf("%d %d", &L, &C); /* 构造字母表 */ setletters; for (int i = 0; i < C; ) { char ch; cin >> ch; letters.insert(ch); i++; } /* 构造BasePsw. */ string basePsw; for (set ::iterator iter = letters.begin(); iter != letters.end(); iter++) { basePsw += *iter; } sort(basePsw.begin(), basePsw.end()); //printf("获得基础字符串: %s\n", basePsw.c_str()); /* 获取按字典序全排列的密码列表. */ // 去重记录 map used; while (next_permutation(basePsw.begin(), basePsw.end())) { // 截取: 将密码截取为指定L位. string temp = string(basePsw, 0, L); // 过滤: 元音和辅音字母不满足条件的密码. if (!limitC(temp)) continue; // 字典序: 对密码进行字典序排列. sort(temp.begin(), temp.end()); // 去重记录: 以便输出时进行判断. if (used[temp] == false) { puts(temp.c_str()); } used[temp] = true; } }
Super bro