这是一个创建于 3558 天前的主题，其中的信息可能已经有所发展或是发生改变。
比如有一个list（A，B , C ,D , E）
选出
AB, AC, AD,AE, BC, BD, BD, CD,CE, DE
如果嵌套的话，应该是 O=n^2
有没好得办法呢？
选出
AB, AC, AD,AE, BC, BD, BD, CD,CE, DE
如果嵌套的话，应该是 O=n^2
有没好得办法呢？
 |
1
66450146 2015-03-03 00:41:00 +08:00
总的数量就是 O(n^2) 啊，肯定不能再减了……
|
 |
2
wecan 2015-03-03 01:11:04 +08:00
I would say there can be no improvements if you do not provide any further prior information. From what you've provided, it seems your problem is enumeration-based, which suggests you have to thoroughly check each and every possible solution for its quality measure.
You may be able to improve if you look into your problem and look for possible priors such as p(AB)=p(B|A)p(A). In this case, for example, you can use dynamic programming to save yourself the time to calculate p(A) for multiple times. Hope this helps. |
 |
3
bugcoder 2015-03-03 01:14:04 +08:00
http://stackoverflow.com/questions/5360220/how-to-split-a-list-into-pairs-in-all-possible-ways
看这个地方，不过真心没看懂那个最优的gatoatigrado的算法， 求高手解释。 |
|
4
wecan 2015-03-03 01:32:04 +08:00
@bugcoder Forgive me if I'm wrong but I don't think it's the same question OP asked. The problem on stackoverflow is to split a list into pairs, where each result is a list (which has been split into pairs). Whereas the OP's problem is to get all possible pairs where each result is just one pair.
Anyways I may have misunderstood OP's problem in my last reply if the problem is purely on the splitting process... |
 |
5
billwsy 2015-03-03 06:45:34 +08:00
@wecan Apparently you have given informative, useful and helpful information. However I am quite curious if there is any specific reason that you reply in English, given you have a lot of posts in Chinese before.
|
 |
6
yegle 2015-03-03 08:18:52 +08:00
强烈怀疑楼主在优化一些可能并不热的代码…
|
Select Language