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;
|
|
