求高效快速的排列组合方法

Question

前不久碰到一个关于排列组合方面的问题,大意如下:
由包含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能匹配求高手指点高效的算法

Answer 1

“d,e,g,c,a,d”你这个怎么有两个d?
应该不能重复才好理解，如果重复，那该匹配哪个d?
产生歧义，楼主好好分析一下.

Answer 2

2楼的兄弟好像没明白我的意思/
字母序列是任意随机的，长度可能有100个
d,e,g,c,a,d在6组中有组匹配，则可以下一组，也就是往后走一步取e,g,c,a,d,e这6个
然后再用6组字母区去匹配，比如e,g,c,a,d,e，则6组中的第一组中有e，就可以再下一组
如此循环，直到最后6个字母能在字母集中匹配到其中一个/不知道我说清楚没

Answer 3

可能描述的有点复杂了
就是比如字母序列为：
d,e,g,c,a,d,e,h,h,j,y,c,a,d,e,h,o,z,d,p,l......（可能有100，1000个组成）
假设求得的结果为这样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那么第一个子序列（前6个）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个可以不管了
继续下一组子序列....

Answer 4

后面会发现子序列[d,e,h,h,j,y]没有一组能在相应位置与之匹配，所以，这6组结果的组合不是问题最终的解

Answer 5

这样，lz先用位运算试试，应该可以提高一些速度，不过，只是常数级的提高。方法是把a,b,c,d 26个字母应视为1 2 4 8 16......，每一组数比如a b d e f就对应60，同给入的数做一个&操作判断是否为0，应该可以。 但如果想从整体提高速度，还需要进一步优化，可以利用类似KMP的方法来减少回溯。

Answer 6

谢谢litaoye 兄弟不过我觉得匹配的方法不是最耗时的，关键是6组结果集的生成，如果全列出来就是 C(26,5)(26选5的组合)，假设结果是S，然后在P(S,6)(S组选6组全排列),再用每个排列结果去匹配，但这个数量级太大了，有没方法能先删减掉S中的部分组合，再排列、
或者有其他更好的方法

Answer 7

好像是顶点覆盖问题，NP的，根据序列，可以得出一堆条件d,e,g,c,a,d,e,h,h,j,y,c,a,d,e,h,o,z,d,p,l比如：第一组有c，可以过的位置包括4,12......
第二组有e，可以过的位置包括1,6......如果某种组合可以覆盖全部位置，那么该组合就是一个合法组合。LZ可以先用贪心试一试求近似。

Answer 8

谢谢litaoye兄弟还有没哪位大神能给点idear 啊 ，木有就结贴了准备/