I**A
发帖数: 2345 | 1 如果需要remove duplicate, 比如输入是aaa，同样的字符串我们只输出一次a, aa, aaa
除了加一个全局变量(for example, HashSet in java) 来记录已有的string之外，有别的好法子没？
就是说，如果输入是"abc"
输出就会是
a
ab
abc
ac
b
bc
c
如果不考虑重复的话，如果输入是"aaa"
输出就会是
a
aa
aaa
aa
a
aa
a
现在呢，我只想要输出（重复的不要）
a
aa
aaa | r*******n
发帖数: 3020 | 2 python code:
23 def combination(a):
24 result = [[]]
25 for i in a:
26 if [i] in result: # 如果当前元素i跟前面木个相同，只添加不拷贝
27 for each in result:
28 each.append(i)
29 result.append([])
30 else:
31 temp=copy.deepcopy(result)
32 for each in temp:
33 each.append(i)
34 result.extend(temp)
35
36 print '\n'.join([str(each) for each in result])
for example:
combination(['a','a','
【在 I**A 的大作中提到】
: 如果需要remove duplicate, 比如输入是aaa，同样的字符串我们只输出一次a, aa, aaa
: 除了加一个全局变量(for example, HashSet in java) 来记录已有的string之外，有别的好法子没？
: 就是说，如果输入是"abc"
: 输出就会是
: a
: ab
: abc
: ac
: b
: bc
| I**A
发帖数: 2345 | 3 不会Python的黯然飘过～～
【在 r*******n 的大作中提到】
: python code:
: 23 def combination(a):
: 24 result = [[]]
: 25 for i in a:
: 26 if [i] in result: # 如果当前元素i跟前面木个相同，只添加不拷贝
: 27 for each in result:
: 28 each.append(i)
: 29 result.append([])
: 30 else:
: 31 temp=copy.deepcopy(result)
| i***1
发帖数: 95 | 4 一个方法是，先按照无重复的方法生成所有的串，然后sort。再扫面一遍，输出不重复
的。
aaa
有别的好法子没？
【在 I**A 的大作中提到】
: 如果需要remove duplicate, 比如输入是aaa，同样的字符串我们只输出一次a, aa, aaa
: 除了加一个全局变量(for example, HashSet in java) 来记录已有的string之外，有别的好法子没？
: 就是说，如果输入是"abc"
: 输出就会是
: a
: ab
: abc
: ac
: b
: bc
| i***1
发帖数: 95 | 5 不对。
for example: input aba
your program will output:
aa, a, aba, ba,[] #missing ab & b in this case
【在 r*******n 的大作中提到】
: python code:
: 23 def combination(a):
: 24 result = [[]]
: 25 for i in a:
: 26 if [i] in result: # 如果当前元素i跟前面木个相同，只添加不拷贝
: 27 for each in result:
: 28 each.append(i)
: 29 result.append([])
: 30 else:
: 31 temp=copy.deepcopy(result)
| p*u
发帖数: 136 | 6 把所有的串生成出来，排序然后去重，这是一个思路。
另一个思路是，不用HashSet，用Trie来保存已有的string集合。本质上和用hashset是
一样的，但是有一些优化。不用每个产生的串都去求hash判断是否已经有了。比如aaa
，产生7个串，{a, a, a, aa, aa, aa, aaa}，用hashset就需要求7次hash，但是用
Trie的开销会稍微小一些。
aaa
有别的好法子没？
【在 I**A 的大作中提到】
: 如果需要remove duplicate, 比如输入是aaa，同样的字符串我们只输出一次a, aa, aaa
: 除了加一个全局变量(for example, HashSet in java) 来记录已有的string之外，有别的好法子没？
: 就是说，如果输入是"abc"
: 输出就会是
: a
: ab
: abc
: ac
: b
: bc
| j***i
发帖数: 1278 | 7 2个小时就学会了
【在 I**A 的大作中提到】
: 不会Python的黯然飘过～～
| w***h
发帖数: 415 | 8 你这个问题不太清除, 比如, bc和cb算重复吗? 如果不算, 就不是组合(combination),
而是排列(permutation)的问题.
aaa
有别的好法子没？
【在 I**A 的大作中提到】
: 如果需要remove duplicate, 比如输入是aaa，同样的字符串我们只输出一次a, aa, aaa
: 除了加一个全局变量(for example, HashSet in java) 来记录已有的string之外，有别的好法子没？
: 就是说，如果输入是"abc"
: 输出就会是
: a
: ab
: abc
: ac
: b
: bc
| I**A
发帖数: 2345 | 9 你说的这个减少求HASH的次数是个good point
可是要考虑到建立Trie的复杂性。。。。
我一向比较favor简单的东西。。
aaa
【在 p*u 的大作中提到】
: 把所有的串生成出来，排序然后去重，这是一个思路。
: 另一个思路是，不用HashSet，用Trie来保存已有的string集合。本质上和用hashset是
: 一样的，但是有一些优化。不用每个产生的串都去求hash判断是否已经有了。比如aaa
: ，产生7个串，{a, a, a, aa, aa, aa, aaa}，用hashset就需要求7次hash，但是用
: Trie的开销会稍微小一些。
:
: aaa
: 有别的好法子没？
| I**A
发帖数: 2345 | 10 真的假的？ 那也木有时间学了
【在 j***i 的大作中提到】
: 2个小时就学会了
| | | I**A
发帖数: 2345 | 11 bc and cb算重复(but the code does not need to generate 'cb' at all for 'abc'
string..)
here combination的定义就是follow traditional definition
http://en.wikipedia.org/wiki/Combination
),
【在 w***h 的大作中提到】
: 你这个问题不太清除, 比如, bc和cb算重复吗? 如果不算, 就不是组合(combination),
: 而是排列(permutation)的问题.
:
: aaa
: 有别的好法子没？
| w***h
发帖数: 415 | 12 比如, bcb为输入, 那输出:
b
bc
bcb
bb
c
cb不应该输出, 你开始的问题没说清这种情况. 为什么hash不够好呢? 这在我看来好象
是最简单的了.
abc'
【在 I**A 的大作中提到】
: bc and cb算重复(but the code does not need to generate 'cb' at all for 'abc'
: string..)
: here combination的定义就是follow traditional definition
: http://en.wikipedia.org/wiki/Combination
:
: ),
| I**A
发帖数: 2345 | 13 啊，对不起，也许我理解有误。
我把自己给饶糊涂了。。
对于bcb这个输入， 输出的cb应该是理解为跟bc不同的还是相同的？？
同学们，你们谁给讲解一下？
我原来想说的意思是，"abc"这个输入，不应该出现cb做为输出。。
HashSet挺好的，问题就是我在实现的时候必须把它设置为instance variable,而不能
用一个local variable..我不是很喜欢这个global变量 idea..
（延伸问题：In "bcb" input case, 如果bc and cb算是重复的，how to check it with HashSet?)
帮我看看，是不是可以改进？
HashSet set = new HashSet();
public void doCombine(char[] instr, StringBuilder outstr, int start,
int end){
for(int i=start; i
outstr.append(instr[i]);
【在 w***h 的大作中提到】
: 比如, bcb为输入, 那输出:
: b
: bc
: bcb
: bb
: c
: cb不应该输出, 你开始的问题没说清这种情况. 为什么hash不够好呢? 这在我看来好象
: 是最简单的了.
:
: abc'
| r*******n
发帖数: 3020 | 14 Thank you, it's wrong.
anyway, ab and ba are treated same in combination,
but It does miss b.
【在 i***1 的大作中提到】
: 不对。
: for example: input aba
: your program will output:
: aa, a, aba, ba,[] #missing ab & b in this case
| w***h
发帖数: 415 | 15 你不是在说笑吧? 你问的问题, 让其他人帮你解释? :)
我JAVA一点不会, 虽然也能看懂你的CODE. 不过,用不用hash和是不是必须用global
variable,有这么紧密的关联, 还是很有创意的哈. :)
严肃的说, 回答你的问题, 我肯定是可以改进的.
with HashSet?)
【在 I**A 的大作中提到】
: 啊，对不起，也许我理解有误。
: 我把自己给饶糊涂了。。
: 对于bcb这个输入， 输出的cb应该是理解为跟bc不同的还是相同的？？
: 同学们，你们谁给讲解一下？
: 我原来想说的意思是，"abc"这个输入，不应该出现cb做为输出。。
: HashSet挺好的，问题就是我在实现的时候必须把它设置为instance variable,而不能
: 用一个local variable..我不是很喜欢这个global变量 idea..
: （延伸问题：In "bcb" input case, 如果bc and cb算是重复的，how to check it with HashSet?)
: 帮我看看，是不是可以改进？
: HashSet set = new HashSet();
| I**A
发帖数: 2345 | 16
不要笑，用不用hash跟global没什么必然关系，我不喜欢global。。。
展开说说怎样改进？
【在 w***h 的大作中提到】
: 你不是在说笑吧? 你问的问题, 让其他人帮你解释? :)
: 我JAVA一点不会, 虽然也能看懂你的CODE. 不过,用不用hash和是不是必须用global
: variable,有这么紧密的关联, 还是很有创意的哈. :)
: 严肃的说, 回答你的问题, 我肯定是可以改进的.
:
: with HashSet?)
| w***h
发帖数: 415 | 17 请问, 你不可以把hash放到你的函数定义里面去吗? 难道你不喜欢什么, 就要做什么不
成? :)
另外, 回答你的延伸问题：In "bcb" input case, 如果bc and cb算是重复的，how to
check it with HashSet? 这是经典的anagram问题, 可以有很多方法, 最不要动脑子
的方法应该是把26个字母对应到26个最小的质数, 比如b->2, c->3,
bc(或者cb)用2x3(3x2)等于6做hash key. 你可以想想其他的有意思的办法, 干点真正
有小创意的事哈, :)
【在 I**A 的大作中提到】
:
: 不要笑，用不用hash跟global没什么必然关系，我不喜欢global。。。
: 展开说说怎样改进？
| I**A
发帖数: 2345 | 18
唉，你以为我没试过麽？我当然试过了不成之后才挪到global外面去的。。。
我纠结递归很久了，没搞明白为嘛放里面不成。。。
to
也是，这个anagram的方法我知道。。
哎，我觉得用prime number来求hash value是需要用脑子的吧
最不用脑子的应该是sort才对
【在 w***h 的大作中提到】
: 请问, 你不可以把hash放到你的函数定义里面去吗? 难道你不喜欢什么, 就要做什么不
: 成? :)
: 另外, 回答你的延伸问题：In "bcb" input case, 如果bc and cb算是重复的，how to
: check it with HashSet? 这是经典的anagram问题, 可以有很多方法, 最不要动脑子
: 的方法应该是把26个字母对应到26个最小的质数, 比如b->2, c->3,
: bc(或者cb)用2x3(3x2)等于6做hash key. 你可以想想其他的有意思的办法, 干点真正
: 有小创意的事哈, :)
| w***h
发帖数: 415 | 19 肯定是你纠结的还不够. :)
【在 I**A 的大作中提到】
:
: 唉，你以为我没试过麽？我当然试过了不成之后才挪到global外面去的。。。
: 我纠结递归很久了，没搞明白为嘛放里面不成。。。
: to
: 也是，这个anagram的方法我知道。。
: 哎，我觉得用prime number来求hash value是需要用脑子的吧
: 最不用脑子的应该是sort才对
| w***h
发帖数: 415 | 20 aha, Java is Pass-by-Value, Dammit! :)
估计你侃侃着片就明白的干活了:
http://javadude.com/articles/passbyvalue.htm
【在 I**A 的大作中提到】
:
: 唉，你以为我没试过麽？我当然试过了不成之后才挪到global外面去的。。。
: 我纠结递归很久了，没搞明白为嘛放里面不成。。。
: to
: 也是，这个anagram的方法我知道。。
: 哎，我觉得用prime number来求hash value是需要用脑子的吧
: 最不用脑子的应该是sort才对
| | | I**A
发帖数: 2345 | 21 这个Java pass primitives by value, object by reference
是臭名昭著的confusing..
这个link不能帮我解释为什么放在函数内部不可以?
不过倒是提醒了我
可以把hashset 的object reference当参数传递 ..:p
public void doCombine(char[] instr, StringBuilder outstr, HashSet<
String> set, int start, int end){
for(int i=start; i
outstr.append(instr[i]);
if(!set.contains(outstr.toString())){
System.out.println(outstr);
set.add(outstr.toString());
}
doCombine(
【在 w***h 的大作中提到】
: aha, Java is Pass-by-Value, Dammit! :)
: 估计你侃侃着片就明白的干活了:
: http://javadude.com/articles/passbyvalue.htm
| t*q
发帖数: 104 | 22 错的吧
['a', 'b', 'b']
【在 r*******n 的大作中提到】
: Thank you, it's wrong.
: anyway, ab and ba are treated same in combination,
: but It does miss b.
| p*u
发帖数: 136 | 23 如果你单单是不想用global变量的话，你把在函数内部new一个就行了，申请的内存空
间也是在heap里的。
anyway，综合来说，我觉得hash是一个比较适合的方法了。
with HashSet?)
【在 I**A 的大作中提到】
: 啊，对不起，也许我理解有误。
: 我把自己给饶糊涂了。。
: 对于bcb这个输入， 输出的cb应该是理解为跟bc不同的还是相同的？？
: 同学们，你们谁给讲解一下？
: 我原来想说的意思是，"abc"这个输入，不应该出现cb做为输出。。
: HashSet挺好的，问题就是我在实现的时候必须把它设置为instance variable,而不能
: 用一个local variable..我不是很喜欢这个global变量 idea..
: （延伸问题：In "bcb" input case, 如果bc and cb算是重复的，how to check it with HashSet?)
: 帮我看看，是不是可以改进？
: HashSet set = new HashSet();
| n*****u
发帖数: 5 | 24 写了个不用hashset的方法，不过太长了点。。需要预处理得到unique letters和count
。不知道有没简洁的解法?
void do_perm(vector& letters, vector& count, string& str, int len)
{
if(str.size()==len) {
cout << str << " ";
return;
}
for(int i=0; i
if(count[i]) {
str.push_back(letters[i]);
--count[i];
do_perm(letters, count, str, len);
++count[i];
str.erase(str.size()-1);
}
}
}
void do_comb(vector | I**A
发帖数: 2345 | 25 nod, i think hash is more reasonable in this case
but 函数内部new不成
depends on where/when the recursive functions are called, the hash set will
be newly initialized among some calls.
so, either global, or pass it as an argument
【在 p*u 的大作中提到】
: 如果你单单是不想用global变量的话，你把在函数内部new一个就行了，申请的内存空
: 间也是在heap里的。
: anyway，综合来说，我觉得hash是一个比较适合的方法了。
:
: with HashSet?)
| r*******n
发帖数: 3020 | 26 ye, it's wrong, forget it.
【在 t*q 的大作中提到】
: 错的吧
: ['a', 'b', 'b']
| w***h
发帖数: 415 | 27 pass-by-ref, function scope, 或者说, class/instance scope (OO) 肯定都可以,
一定是你纠结地不够. :)
我肯定JAVA不会这么简单的几种方式都做不了.最简单地说, 难道JAVA没有静态变量?
你不可以用结构/类? 等等... 问题应该是方法太多, 哪个对你实际问题最合适, 而不
会是做不了.
will
【在 I**A 的大作中提到】
: nod, i think hash is more reasonable in this case
: but 函数内部new不成
: depends on where/when the recursive functions are called, the hash set will
: be newly initialized among some calls.
: so, either global, or pass it as an argument
| I**A
发帖数: 2345 | 28 分特，JAVA AND IAYA这么像。。
你说的有道理。。
可是我就是没想出来。
SIGH,不想了
事儿太多。。
【在 w***h 的大作中提到】
: pass-by-ref, function scope, 或者说, class/instance scope (OO) 肯定都可以,
: 一定是你纠结地不够. :)
: 我肯定JAVA不会这么简单的几种方式都做不了.最简单地说, 难道JAVA没有静态变量?
: 你不可以用结构/类? 等等... 问题应该是方法太多, 哪个对你实际问题最合适, 而不
: 会是做不了.
:
: will
| d**e
发帖数: 6098 | 29 c++有函数里定义static变量，那么递归其实也是只是一个变量。
我以为java也可以这么定义，但发觉java不能在函数里面定义static变量。
【在 I**A 的大作中提到】
: 分特，JAVA AND IAYA这么像。。
: 你说的有道理。。
: 可是我就是没想出来。
: SIGH,不想了
: 事儿太多。。
| I**A
发帖数: 2345 | 30 我的理解是这样的
in java, "static" keyword is used to define class variable/method, so we can
't use it within a method
【在 d**e 的大作中提到】
: c++有函数里定义static变量，那么递归其实也是只是一个变量。
: 我以为java也可以这么定义，但发觉java不能在函数里面定义static变量。
|
|
