String permunation question (CS) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

String permunation question (CS)

String permunation question (CS)# JobHunting - 待字闺中

l*r2013-12-31 08:12

1 楼

Old question, but can't find a good and easy to understand answer.
What happens if there are duplicate letters in the string? like, abcdd.

p*22013-12-31 08:12

2 楼

You shouldn't output duplicate permutations.

r*c2013-12-31 08:12

3 楼

use recursive, fix the first letter then do permutation for the rest n-1.

【在 l********r 的大作中提到】

: Old question, but can't find a good and easy to understand answer.
: What happens if there are duplicate letters in the string? like, abcdd.

l*r2013-12-31 08:12

4 楼

It asks to handle the case where there are duplicate letters in the input
string.

s*x2013-12-31 08:12

5 楼

use or implement your own std::next_permutation

x*82013-12-31 08:12

6 楼

Easy way is use set, you cannot store duplicate keys in set :D
Or you can do some check, e.g aabc,
if(i>0&&str[i]==str[i-1]&&!flag[i-1]) continue;

【在 l********r 的大作中提到】

: It asks to handle the case where there are duplicate letters in the input
: string.

p*22013-12-31 08:12

7 楼

p = (x) -> console.log x
swap = (arr, i, j) -> [arr[i], arr[j]] = [arr[j], arr[i]]
dfs = (arr, curr) ->
if curr is arr.length
p arr.join("")
return
set = {}
for i in [curr...arr.length]
unless set[arr[i]]
set[arr[i]]=true
swap arr, curr, i
dfs arr, curr+1
swap arr, curr, i
permutation = (str) -> dfs str.split(""), 0

l*n2013-12-31 08:12

8 楼

递归并用一个Boolean[26],记录是否用过某个字符作为开头了。

【在 l********r 的大作中提到】

: Old question, but can't find a good and easy to understand answer.
: What happens if there are duplicate letters in the string? like, abcdd.

h*o2013-12-31 08:12

9 楼

我用swap那种解法理解的。去duplicate就加上noswap（）判断。
bool noswap(int level, int i, const vector& num){
for (int j=level;jif (num[j]==num[i]){
return true;
}
}
return false;
}

void perm_recur(vector &num, int size, int level, vector> >& results) {
if (level == size) {results.push_back(num); return;}
for (int i = level; i < size; i++){
if (noswap(level, i, num)) continue;
swap(num[level], num[i]);
perm_recur(num, size, level+1, results);
swap(num[level], num[i]);
}
}

【在 l********r 的大作中提到】

: Old question, but can't find a good and easy to understand answer.
: What happens if there are duplicate letters in the string? like, abcdd.