r******e
发帖数: 80 | 1 how to get all permutation of a string if there are duplications?
想了很久，想不出方法。 请大家看看有没有比较好的思路。 | x*****p
发帖数: 1707 | 2 Using recursive for permutation, and put it into a set which automatically
remove duplicates, then output the set. | r******e
发帖数: 80 | 3 谢谢， xiongyp
1. 如果没有空间存在set里面呢？
2. 另外，对于n长度的字符串， 其中有m个相同的字符， 其它的都是唯一的。 复杂度
是 n!. 有没有办法做到 n! / m! 呢？ | l*****a
发帖数: 14598 | 4 step1: sort input string
step2:
for(int i=start;i
{
if(i!=start)&&(str[i]==str[i-1]) continue;
swap(str[i],str[start]);
func(i+1,str);
swap(str[i],str[start]);
}
【在 r******e 的大作中提到】
: how to get all permutation of a string if there are duplications?
: 想了很久，想不出方法。 请大家看看有没有比较好的思路。
| i**9
发帖数: 351 | 5 讲讲原因？
【在 l*****a 的大作中提到】
: step1: sort input string
: step2:
: for(int i=start;i: {
: if(i!=start)&&(str[i]==str[i-1]) continue;
: swap(str[i],str[start]);
: func(i+1,str);
: swap(str[i],str[start]);
: }
| f***g
发帖数: 214 | 6 仅仅判断(str[i]==str[i-1])
还不够
要看str[start]和str[i-1]之间有没有str[i]
【在 l*****a 的大作中提到】
: step1: sort input string
: step2:
: for(int i=start;i: {
: if(i!=start)&&(str[i]==str[i-1]) continue;
: swap(str[i],str[start]);
: func(i+1,str);
: swap(str[i],str[start]);
: }
| x*****p
发帖数: 1707 | 7 1. 先用一个Hashtable统计每个字符出现的频率：(c_1, v_1), (c_2, v_2), ..., (c_
k, v_k)
2. 做一个长度为n的字符数组，填入c_1入v_1的位置，有C(n, v_1)种填法，每一种填
法，剩下的位置填入v_2个c_2，用递归算法填完后面所有的字符。 |
|
