求高效快速的排列组合方法
前不久碰到一个关于排列组合方面的问题,大意如下:
由包含a,b,c,d....x,y,z这26个字母组成的随机字母序列: d,e,g,c,a,d,e,h,h,j,y,c,a,d,e,h,o,z,d,p,l.....
希望求得6组字母的组合集，每组5个字母，使得上述字母序列中任意6个连续的字母至少有一个在字母组合集中，顺序需和组合集相同。 序列中任意6个连续的字母就像一条路径，要从组合集穿过，但不让它穿过，也就是能至少匹配到一个/
例如：字母的组合集为
1. g,r,e,h,a
2. l,d,t,w,b
3. p,o,y,v,c
4. c,k,f,d,y
5. u,h,d,s,h
6. a,x,n,v,g
去匹配序列中第一个子序列：d,e,g,c,a,d，则第四组c能匹配 具体如下
d,e,g,c,a,d按顺序在6组结果中找，即
d in( g,r,e,h,a )? =>false
e in(l,d,t,w,b)? =>false
g in(p,o,y,v,c )? =>false
c in(c,k,f,d,y)? =>true 到这里就成功了，后面两个a,d可以不看了
然后下一组子序列e,g,c,a,d,e,也就是指针从序列的第一个位置加1，指向第2个，再从指针位置往后取6个字母形成新的子序列，再匹配：
e in( g,r,e,h,a )? =>true ,后面5个可以不管了
继续下一组子序列....
但后面会发现子序列[d,e,h,h,j,y]没有一组能在相应位置与之匹配，所以，这6组结果的组合不是问题最终的解
求高手指点高效的算法
[ 本帖最后由 zhang87224088 于 2011-4-18 11:11 编辑 ]
|
