首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 网站开发 > 高性能WEB开发 >

求好手算法逻辑,JAVA实现多环节统计

2013-04-09 
求高手算法逻辑,JAVA实现多环节统计有多条环节路线,需将路线出现三个及以上环节点进行统计,不按顺序。例:有

求高手算法逻辑,JAVA实现多环节统计
有多条环节路线,需将路线出现三个及以上环节点进行统计,不按顺序。例:有路线(1)A-B-C-D-F-D,(2)A-F-C,(3)A-B-F-K-Z-D统计结果:第1条路线和第2条路线都出现了A,C,F节点,统计有2条,第3条路线和第1条路线出现A,B,F,D 也统计有2条。 
只想到了在代码里利用递归的方法将每一条路线都拆分(如下将第一条路线的拆分结果),再将每个路线组合进行匹配。这样如果一条路线出现节点比较多,数据就成倍增长了。判断下来很耗资源。求比较高效的解决办法。

第一条路线拆分结果:
当取3个数时有20个可能.结果为:
[A, B, C]
[A, B, D]
[A, B, F]
[A, B, D]
[A, C, D]
[A, C, F]
[A, C, D]
[A, D, F]
[A, D, D]
[A, F, D]
[B, C, D]
[B, C, F]
[B, C, D]
[B, D, F]
[B, D, D]
[B, F, D]
[C, D, F]
[C, D, D]
[C, F, D]
[D, F, D]

当取4个数时有15个可能.结果为:
[A, B, C, D]
[A, B, C, F]
[A, B, C, D]
[A, B, D, F]
[A, B, D, D]
[A, B, F, D]
[A, C, D, F]
[A, C, D, D]
[A, C, F, D]
[A, D, F, D]
[B, C, D, F]
[B, C, D, D]
[B, C, F, D]
[B, D, F, D]
[C, D, F, D]

当取5个数时有6个可能.结果为:
[A, B, C, D, F]
[A, B, C, D, D]
[A, B, C, F, D]
[A, B, D, F, D]
[A, C, D, F, D]
[B, C, D, F, D]

当取6个数时有1个可能.结果为:
[A, B, C, D, F, D]

最终结果数:42 算法 java 统计?数据量大
[解决办法]
“其实只需考虑到哪条路线出现了三个或以上相同的节点(不按顺序)就归类”这个我能否理解为对所有出现过的且节点集超过3个的组合都要统计在内?
如果是以上说法,那么不可避免的结果数据会很庞大,提供一中递归的方法(伪代码),希望能帮上忙

Map countMap;//用于记录数据

function(String subLine,int index, List line) {//当前线路组合,递归到第几个节点,线路
    如果  subLine.size() >= 3 countMap记录subLine组合的数据
    如果 index >= line.size() return;
    function(subLine,index + 1);//不加当前节点
    function(subLine + line.get(index),index + 1);//加入当前节点
}

调用方式
for(line:lines) {//遍历,如果保留了上面的countMap数据就可以不用对前面统计的数据重复统计,从而也可以做分布式的统计。
    line.sort();先给线路做一点规则的排序
    function("",0,line);
}

热点排行