x*****m 发帖数: 29 | 1 看过很多permutation算法 都是看了就忘忘了再看看了还是忘
即使是Dijkstra爷爷的那个很简洁的...毕竟不是自己想的...觉得还是不容易记..
于是刚才就想写一个容易理解容易记忆的,跟大家分享一下,轻拍...是recursive的 所
以空间代价不是那么理想 但是容易
记...
受那道经典的洗牌算法的启发, 基本就是n个位置,从s[0]到s[n-1]
先是排定第一个位置,依次拿s[0]~s[n-1]跟s[0]交换
每交换一次,对剩下的字符串再进行递归的操作
直到n个位置排定了,输出排列结果
(语言能力日益下降,不知道讲清楚没)
current是现在正在排定的位置, len是要排的字符的长度,从s的尾部开始数len个
swap是随便一个实现交换char的函数
code如下:
void Permutate(std::string s, int len) {
size_t i;
if (len == 1) {
std::cout << s << std::endl;
return;
}
int c | m******9 发帖数: 968 | 2 还可以考虑一下 permutation时,不打印重复string的写法。
另外还有combination的写法。
把你所写的代码调整一下就可以。 | x*****m 发帖数: 29 | 3 恩 :-) 正在写呢 周四电面 打算最后这几天看看基本的东西 觉得其实基本的反而
容易忘...
【在 m******9 的大作中提到】 : 还可以考虑一下 permutation时,不打印重复string的写法。 : 另外还有combination的写法。 : 把你所写的代码调整一下就可以。
| P*******b 发帖数: 1001 | 4 有重复元素怎么弄?谁指点一下?
【在 x*****m 的大作中提到】 : 看过很多permutation算法 都是看了就忘忘了再看看了还是忘 : 即使是Dijkstra爷爷的那个很简洁的...毕竟不是自己想的...觉得还是不容易记.. : 于是刚才就想写一个容易理解容易记忆的,跟大家分享一下,轻拍...是recursive的 所 : 以空间代价不是那么理想 但是容易 : 记... : 受那道经典的洗牌算法的启发, 基本就是n个位置,从s[0]到s[n-1] : 先是排定第一个位置,依次拿s[0]~s[n-1]跟s[0]交换 : 每交换一次,对剩下的字符串再进行递归的操作 : 直到n个位置排定了,输出排列结果 : (语言能力日益下降,不知道讲清楚没)
| s*******e 发帖数: 93 | 5 This website has mentioned a way to consider duplicates,
http://n1b-algo.blogspot.com/2009/01/string-permutations.html
but I have tried it, and it seems to have some bugs. Anyone else try this
method?
Basically it maintains a "previous" variable for the s[i],and check if s[i]
equals to previous before doing the first swapping. | P*******b 发帖数: 1001 | 6 好像不对。等待那位高人解答一下。
]
【在 s*******e 的大作中提到】 : This website has mentioned a way to consider duplicates, : http://n1b-algo.blogspot.com/2009/01/string-permutations.html : but I have tried it, and it seems to have some bugs. Anyone else try this : method? : Basically it maintains a "previous" variable for the s[i],and check if s[i] : equals to previous before doing the first swapping.
| v********w 发帖数: 136 | 7 这样行不
void Permutate(string &s, int len) {
size_t i;
hashmap hm;
for (i=0;i<26;i++) hash[i]=0;
if (len == 1) {
cout << s << endl;
return;
}
int current = s.size() - len;
for (i=s.size()-len; i
if(!hm.contains(s[i]))
{ hm.add(s[i]);
Swap(s[current], s[i]);
Permutate(s, len - 1);
Swap(s[current], s[i]);
}
}
}
【在 P*******b 的大作中提到】 : 好像不对。等待那位高人解答一下。 : : ]
| P*******b 发帖数: 1001 | 8 不知道行不行啊。
好多额外空间啊。
【在 v********w 的大作中提到】 : 这样行不 : void Permutate(string &s, int len) { : size_t i; : hashmap hm; : : for (i=0;i<26;i++) hash[i]=0; : if (len == 1) { : cout << s << endl; : : return;
|
|